Navegar

Colección

Datos Estadísticas

Artículo

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:

Edge modification problems in graphs have a lot of applications in different areas. Polynomial time algorithms and NP-completeness results appear in several works in the literature. In this paper, we prove new complexity results of these problems in some graph classes, such as, interval, circular-arc, permutation, circle, bridge and weakly chordal graphs. © 2004 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Computational complexity of edge modification problems in different classes of graphs
Autor:Burzyn, P.; Bonomo, F.; Durán, G.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile
Palabras clave:computational complexity; edge modification problems; graph classes
Año:2004
Volumen:18
Página de inicio:41
Página de fin:46
DOI: http://dx.doi.org/10.1016/j.endm.2004.06.007
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_v18_n_p41_Burzyn

Referencias:

  • Bodlaender, H., De Fluiter, B., On intervalizing k-colored graphs for DNA physical mapping (1966) Disc. App. Math., 71, pp. 55-77
  • Booth, K., Lueker, G., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms (1976) J. Comp. Sci., 13, pp. 335-379
  • Brandstädt, A., Le, V., Spinrad, J., (1999) Graph Classes: A Survey, , SIAM
  • Dushnik, B., Miller, E., Partially ordered sets (1941) Amer. J. Math., 63, pp. 600-610
  • El-Mallah, E., Colbourn, C., The complexity of some edge deletion problems (1988) IEEE Trans. Circ. Syst., 35 (3), pp. 354-362
  • Farber, M., Jamison, R., On local convexity in graphs (1987) Disc. Math., 66, pp. 231-247
  • Garey, M., Jonhson, D., (1979) Computers and Intractability: A Guide to the Theory of NP- Completeness, , Freeman and Co
  • Garey, M., Johnson, D., Stockmeyer, L., Some simplified NP-complete graph problems (1976) Theor. Comp. Sci., 1, pp. 237-267
  • Garey, M., Johnson, D., Tarjan, R., The planar Hamiltonian circuit problem is NP-complete (1976) SIAM J. Comp., 5, pp. 704-714
  • Goldberg, P., Golumbic, M., Kaplan, H., Shamir, R., Four strikes against physical mapping of DNA (1995) J. Comp. Biol., 2, pp. 139-152
  • Golumbic, M., (1980) Algorithmic Graph Theory and Perfect Graphs, , Acad. Press
  • Golumbic, M., Kaplan, H., Shamir, R., On the complexity of DNA physical mapping (1994) Advances in App. Math., 15, pp. 251-261
  • Hakimi, S., Schmeichel, E., Young, N., Orienting graphs to optimize reachability (1997) Inform. Proc. Letters, 63, pp. 229-235
  • Hammer, P., Simeone, B., The splittance of a graph (1981) Combinatorica, 1, pp. 275-284
  • Margot, F., Some complexity results about threshold graphs (1994) Disc. App. Math., 49, pp. 229-308
  • McConnell, R., Spinrad, J., Linear-time transitive orientation (1997) Proc. 8th Ann. ACM-SIAM Symp. on Disc. Algorithms, New Orleans, pp. 19-25
  • Natanzon, A., Shamir, R., Sharan, R., Complexity classification of some edge modifications problems (2001) Disc. App. Math., 113, pp. 109-128
  • Rose, J., A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations (1972) Graph Theory and Computing, pp. 183-217. , Reed R.C. (Ed), Acad. Press
  • Spinrad, J., Recognition of circle graphs (1994) J. of Algorithms, 16 (2), pp. 264-282
  • Spinrad, J., Sritharan, R., Algorithms for weakly triangulated graphs (1995) Disc. App. Math., 59, pp. 181-191
  • Tucker, A., Matrix characterizations of circular-arc graphs (1971) Pacific J. Math., 38, pp. 535-545
  • Yannakakis, M., Computing the minimum fill-in is NP-complete (1981) SIAM J. Alg. Disc. Math., 2 (1), pp. 77-79
  • Yannakakis, M., Edge deletion problems (1981) SIAM J. Comp., 10 (2), pp. 297-309

Citas:

---------- APA ----------
Burzyn, P., Bonomo, F. & Durán, G. (2004) . Computational complexity of edge modification problems in different classes of graphs. Electronic Notes in Discrete Mathematics, 18, 41-46.
http://dx.doi.org/10.1016/j.endm.2004.06.007
---------- CHICAGO ----------
Burzyn, P., Bonomo, F., Durán, G. "Computational complexity of edge modification problems in different classes of graphs" . Electronic Notes in Discrete Mathematics 18 (2004) : 41-46.
http://dx.doi.org/10.1016/j.endm.2004.06.007
---------- MLA ----------
Burzyn, P., Bonomo, F., Durán, G. "Computational complexity of edge modification problems in different classes of graphs" . Electronic Notes in Discrete Mathematics, vol. 18, 2004, pp. 41-46.
http://dx.doi.org/10.1016/j.endm.2004.06.007
---------- VANCOUVER ----------
Burzyn, P., Bonomo, F., Durán, G. Computational complexity of edge modification problems in different classes of graphs. Electron. Notes Discrete Math. 2004;18:41-46.
http://dx.doi.org/10.1016/j.endm.2004.06.007