Navegar

Colección

Datos Estadísticas

Artículo

Groshaus, M.; Hell, P.; Klein, S.; Nogueira, L.T.; Protti, F. "Cycle transversals in bounded degree graphs" (2009) Electronic Notes in Discrete Mathematics. 35(C):189-195
La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

In this work we consider the problem of finding a minimum Ck-transversal (a subset of vertices hitting all the induced chordless cycles with k vertices) in a graph with bounded maximum degree. In particular, we seek for dichotomy results as follows: for a fixed value of k, finding a minimum Ck-transversal is polynomial-time solvable if k ≤ p, and NP-hard otherwise. © 2009 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Cycle transversals in bounded degree graphs
Autor:Groshaus, M.; Hell, P.; Klein, S.; Nogueira, L.T.; Protti, F.
Filiación:Universidad de Buenos Aires, FCEyN, Dpto de Computación, Argentina
Simon Fraser University, Canada
Universidade Federal do Rio de Janeiro (UFRJ), Brazil
Universidade Federal Fluminense (UFF), Brazil
Palabras clave:H-free graph; H-subgraph; H-transversal; transversal
Año:2009
Volumen:35
Número:C
Página de inicio:189
Página de fin:195
DOI: http://dx.doi.org/10.1016/j.endm.2009.11.032
Título revista:Electronic Notes in Discrete Mathematics
Título revista abreviado:Electron. Notes Discrete Math.
ISSN:15710653
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p189_Groshaus

Referencias:

  • Cornaz, D., Mahjoub, A.R., The maximum induced bipartite subgraph problem with edge weights Submitted manuscript; Fishburn, P.C., (1985) Interval Orders and Interval Graphs, , Wiley, New York
  • Garey, M.R., Johnson, D.S., (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, , W. H. Freeman, New York
  • Golumbic, M.C., (1980) Algorithmic Graph Theory and Perfect Graphs, , Wiley, New York
  • Manic, G., Wakabayashi, Y., Packing triangles in low-degree graphs and indifference graphs (2005) Proc. European Conference on Combinatorics, Graph Theory and Applications (EuroComb'05), Berlin, Germany, 2005. Discrete Mathematics and Theoretical Computer Science (DMTCS), AE, pp. 251-256
  • Yannakakis, M., Node- and edge-deletion NP-complete problems (1978) Proc. of the Tenth Annual ACM Symposium on Theory of Computing - STOC'78, pp. 253-264. , ACM Press

Citas:

---------- APA ----------
Groshaus, M., Hell, P., Klein, S., Nogueira, L.T. & Protti, F. (2009) . Cycle transversals in bounded degree graphs. Electronic Notes in Discrete Mathematics, 35(C), 189-195.
http://dx.doi.org/10.1016/j.endm.2009.11.032
---------- CHICAGO ----------
Groshaus, M., Hell, P., Klein, S., Nogueira, L.T., Protti, F. "Cycle transversals in bounded degree graphs" . Electronic Notes in Discrete Mathematics 35, no. C (2009) : 189-195.
http://dx.doi.org/10.1016/j.endm.2009.11.032
---------- MLA ----------
Groshaus, M., Hell, P., Klein, S., Nogueira, L.T., Protti, F. "Cycle transversals in bounded degree graphs" . Electronic Notes in Discrete Mathematics, vol. 35, no. C, 2009, pp. 189-195.
http://dx.doi.org/10.1016/j.endm.2009.11.032
---------- VANCOUVER ----------
Groshaus, M., Hell, P., Klein, S., Nogueira, L.T., Protti, F. Cycle transversals in bounded degree graphs. Electron. Notes Discrete Math. 2009;35(C):189-195.
http://dx.doi.org/10.1016/j.endm.2009.11.032