Registro:
Documento: |
Artículo
|
Título: | NP-completeness results for edge modification problems |
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; NP-completeness; Algorithms; Computational complexity; Graph theory; Set theory; Theorem proving; Edge modification problems; Graph classes; NP-completeness; Problem solving |
Año: | 2006
|
Volumen: | 154
|
Número: | 13 SPEC ISS
|
Página de inicio: | 1824
|
Página de fin: | 1844
|
DOI: |
http://dx.doi.org/10.1016/j.dam.2006.03.031 |
Título revista: | Discrete Applied Mathematics
|
Título revista abreviado: | Discrete Appl Math
|
ISSN: | 0166218X
|
CODEN: | DAMAD
|
PDF: | https://bibliotecadigital.exactas.uba.ar/download/paper/paper_0166218X_v154_n13SPECISS_p1824_Burzyn.pdf |
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v154_n13SPECISS_p1824_Burzyn |
Referencias:
- Bodlaender, H., De Fluiter, B., On intervalizing k-colored graphs for DNA physical mapping (1966) Discrete Appl. 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. Comput. Sci. Technol., 13, pp. 335-379
- Brandstädt, A., Le, V., Spinrad, J., (1999) Graph Classes: A Survey, , SIAM, Philadelphia
- Burzyn, P., Bonomo, F., Durán, G., Computational complexity of edge modification problems in different classes of graphs (2004) Electron. Notes Discrete Math., 18, pp. 41-46
- Chudnovsky, M., Cornuéjols, G., Liu, X., Seymour, P., Vušković, K., Recognizing Berge Graphs (2005) Combinatorica, 25, pp. 143-187
- Deng, X., Hell, P., Huang, J., Linear time representation algorithms for proper circular-arc graphs and proper interval graphs (1996) SIAM J. Comput., 25, pp. 390-403
- Durán, G., Some new results on circle graphs (2003) Matemática Contemporânea, 25, pp. 91-106
- Durán, G., Gravano, A., McConnell, R., Spinrad, J., Tucker, A., Polynomial time recognition of unit circular-arc graphs (2006) J. Algorithms, 58, pp. 67-78
- Durán, G., Lin, M., Clique graphs of Helly circular-arc graphs (2001) Ars Combinatoria, 60, pp. 255-271
- 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. Circuits Systems, 35 (3), pp. 354-362
- Farber, M., Jamison, R., On local convexity in graphs (1987) Discrete Math., 66, pp. 231-247
- Garey, M., Johnson, D., (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, , Freeman and Company, San Francisco
- Garey, M., Johnson, D., Stockmeyer, L., Some simplified NP-complete graph problems (1976) Theoret. Comput. Sci., 1 (3), pp. 237-267
- Goldberg, P., Golumbic, M., Kaplan, H., Shamir, R., Four strikes against physical mapping of DNA (1995) J. Comput. Biol., 2, pp. 139-152
- Golumbic, M., (1980) Algorithmic Graph Theory and Perfect Graphs, , Academic Press, New York
- Golumbic, M., Kaplan, H., Shamir, R., On the complexity of DNA physical mapping (1994) Adv. in Appl. Math., 15, pp. 251-261
- Hakimi, S., Schmeichel, E., Young, N., Orienting graphs to optimize reachability (1997) Inform. Process. Lett., 63, pp. 229-235
- Hammer, P., Simeone, B., The splittance of a graph (1981) Combinatorica, 1, pp. 275-284
- Lekkerkerker, C., Boland, D., Representation of finite graphs by a set of intervals on the real line (1962) Fundamenta Mathematicae, 51, pp. 45-64
- Margot, F., Some complexity results about threshold graphs (1994) Discrete Appl. Math., 49, pp. 229-308
- McConnell, R., Linear-time recognition of circular-arc graphs (2003) Algorithmica, 37 (2), pp. 93-147
- Natanzon, A., Shamir, R., Sharan, R., Complexity classification of some edge modification problems (2001) Discrete Appl. Math., 113, pp. 109-128
- Prisner, E., Bicliques in graphs I: bounds on their number (2000) Combinatorica, 20 (1), pp. 109-117
- 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), Academic Press, New York
- Spinrad, J., Recognition of circle graphs (1994) J. Algorithms, 16 (2), pp. 264-282
- Spinrad, J., Sritharan, R., Algorithms for weakly triangulated graphs (1995) Discrete Appl. Math., 59, pp. 181-191
- Szwarcfiter, J., Recognizing clique-Helly graphs (1997) Ars Combinatoria, 45, pp. 29-32
- Szwarcfiter, J., Bornstein, C., Clique graphs of chordal and path graphs (1994) SIAM J. Discrete Math., 7, pp. 331-336
- Yannakakis, M., Computing the minimum fill-in is NP-complete (1981) SIAM J. Algebraic Discrete Methods, 2 (1), pp. 77-79
- Yannakakis, M., Edge deletion problems (1981) SIAM J. Comput., 10 (2), pp. 297-309
Citas:
---------- APA ----------
Burzyn, P., Bonomo, F. & Durán, G.
(2006)
. NP-completeness results for edge modification problems. Discrete Applied Mathematics, 154(13 SPEC ISS), 1824-1844.
http://dx.doi.org/10.1016/j.dam.2006.03.031---------- CHICAGO ----------
Burzyn, P., Bonomo, F., Durán, G.
"NP-completeness results for edge modification problems"
. Discrete Applied Mathematics 154, no. 13 SPEC ISS
(2006) : 1824-1844.
http://dx.doi.org/10.1016/j.dam.2006.03.031---------- MLA ----------
Burzyn, P., Bonomo, F., Durán, G.
"NP-completeness results for edge modification problems"
. Discrete Applied Mathematics, vol. 154, no. 13 SPEC ISS, 2006, pp. 1824-1844.
http://dx.doi.org/10.1016/j.dam.2006.03.031---------- VANCOUVER ----------
Burzyn, P., Bonomo, F., Durán, G. NP-completeness results for edge modification problems. Discrete Appl Math. 2006;154(13 SPEC ISS):1824-1844.
http://dx.doi.org/10.1016/j.dam.2006.03.031