Linear-time algorithms for eliminating claws in graphs | ||
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación | |
| dc.conicet.organizacion | Universidade Federal de Goiás | |
| dc.conicet.organizacion | Universidade do Estado de Rio do Janeiro | |
| dc.conicet.organizacion | Universidade Federal Fluminense | |
| dc.conicet.organizacion | Universidade Federal do Rio de Janeiro | |
| dc.conicet.organizacion | Universidade do Estado de Rio do Janeiro | |
| dc.contributor.author | Bonomo, Flavia | |
| dc.contributor.author | Nascimento, Julliano R. | |
| dc.contributor.author | Oliveira, Fabiano S. | |
| dc.contributor.author | Souza, Uéverton S. | |
| dc.contributor.author | Szwarcfiter, Jayme L. | |
| dc.date.issued | 2021-12 | |
| dc.description.abstract | Since many (Formula presented.) -complete graph problems are polynomial-time solvable when restricted to claw-free graphs, we study the problem of determining the distance of a given graph to a claw-free graph, considering vertex elimination a measure. Claw-free Vertex Deletion (CFVD) consists of determining the minimum number of vertices to be removed from a graph such that the resulting graph is claw-free. Although CFVD is (Formula presented.) -hard in general and recognizing claw-free graphs is still a challenge, where the current best deterministic algorithm for a graph G consists of performing (Formula presented.) executions of the best algorithm for matrix multiplication, we present linear-time algorithms for CFVD on weighted block graphs and weighted graphs with bounded treewidth. Furthermore, we show that this problem on forests can be solved in linear time by a simpler algorithm, and we determine the exact values for full k-ary trees. On the other hand, we show that CFVD is (Formula presented.) -hard even when the input graph is a split graph. We also show that the problem is hard to be approximated within any constant factor better than 2, assuming the unique games conjecture. | es |
| dc.description.fil | Fil: Bonomo, Flavia. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación; Argentina | |
| dc.description.fil | Fil: Nascimento, Julliano R.. Universidade Federal de Goiás; Brasil | |
| dc.description.fil | Fil: Oliveira, Fabiano S.. Universidade do Estado de Rio do Janeiro; Brasil | |
| dc.description.fil | Fil: Souza, Uéverton S.. Universidade Federal Fluminense; Brasil | |
| dc.description.fil | Fil: Szwarcfiter, Jayme L.. Universidade Federal do Rio de Janeiro; Brasil. Universidade do Estado de Rio do Janeiro; Brasil | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Bonomo, Flavia; Nascimento, Julliano R.; Oliveira, Fabiano S.; Souza, Uéverton S.; Szwarcfiter, Jayme L.; Linear-time algorithms for eliminating claws in graphs; John Wiley & Sons; International Transactions in Operational Research; 31; 1; 12-2021; 296-315 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0969-6016 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/258651 | |
| dc.journal.number | 1 | es |
| dc.journal.pagination | 296-315 | es |
| dc.journal.pais | Reino Unido | es |
| dc.journal.title | International Transactions in Operational Research | es |
| dc.journal.volume | 31 | es |
| dc.language.iso | eng | es |
| dc.publisher | John Wiley & Sons | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1111/itor.13100 | |
| dc.rights | info:eu-repo/semantics/restrictedAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | CLAW-FREE GRAPH | es |
| dc.subject | VERTEX DELETION | es |
| dc.subject | WEIGHTED VERTEX DELETION | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Linear-time algorithms for eliminating claws in graphs | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.6e8e4d7d-9cc3-4ae7-a3ea-97e98a5ddf48_B.pdf
- Tamaño:
- 546.33 KB
- Formato:
- Adobe Portable Document Format