Artículos de revistas
The Graph Sandwich Problem For P4-sparse Graphs
Registro en:
Discrete Mathematics. , v. 309, n. 11, p. 3664 - 3673, 2009.
0012365X
10.1016/j.disc.2008.01.014
2-s2.0-67349134537
Autor
Dantas S.
Klein S.
de Mello C.P.
Morgana A.
Institución
Resumen
The P4-sparse Graph Sandwich Problem asks, given two graphs G1 = (V, E1) and G2 = (V, E2), whether there exists a graph G = (V, E) such that E1 ⊆ E ⊆ E2 and G is P4-sparse. In this paper we present a polynomial-time algorithm for solving the Graph Sandwich Problem for P4-sparse graphs. © 2008 Elsevier B.V. All rights reserved. 309 11 3664 3673 Brandstädt, A., Le, V.B., Spinrad, J.P., (1999) Graphs Classes: A Survey. SIAM Monographs on Discrete Math. and Applications, , Philadelphia Cerioli, M., Everett, H., de Figueiredo, C.M.H., Klein, S., The homogeneous set sandwich problem (1998) Inform. Process. Lett., 67 (1), pp. 31-35 Corneil, D.G., Lerchs, H., Stewart Burlingham, L., Complement reducible graphs (1981) Discrete Appl. Math., 3, pp. 163-174 Corneil, D.G., Perl, Y., Stewart, L.K., A linear recognition algorithm for cographs (1985) SIAM J. Comput., 14, pp. 926-934 Dantas, S., de Figueiredo, C.M.H., Faria, L., On decision and optimization (k, l)-graph sandwich problems (2004) Discrete Appl. Math., 143, pp. 155-165 de Figueiredo, C.M.H., Klein, S., Vusković, K., The Graph Sandwich Problem for 1-Join Composition is NP-complete (2002) Discrete Appl. Math., 121, pp. 73-82 de Figueiredo, C.M.H., Faria, L., Klein, S., Sritharan, R., On the Complexity of sandwich problems for strongly chordal graphs and chordal bipartite graphs Theoret. Comput. Sci, , in press Garey, M.R., Johnson, D.S., (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, , W. H. Freeman and Co., San Francisco Golumbic, M.C., (1980) Algorithmic graph theory and perfect graphs, , Academic Press, New York Golumbic, M.C., Matrix sandwich problems (1998) Linear Algebra Appl., 277, pp. 239-251 Golumbic, M.C., Kaplan, H., Shamir, R., Graph sandwich problems (1995) J. Algorithms, 19 (3), pp. 449-473 Golumbic, M.C., Wassermann, A., Complexity and algorithms for graph and hypergraph sandwich problems (1998) Graphs Combin., 14 (3), pp. 223-239 Hoàng, C.T., (1983) A class of perfect graphs, , M.Sc. Thesis, School of Computer Science, McGill University, Montreal Jamison, B., Olariu, S., P4-reducible graphs, a class of uniquely tree representable graphs (1989) Stud. Appl. Math., 81, pp. 79-87 Jamison, B., Olariu, S., Recognizing P4-sparse graphs in linear time (1992) SIAM J. Comput., 21 (2), pp. 381-406 Jamison, B., Olariu, S., A tree representation for P4-sparse graphs (1992) Discrete Appl. Math., 35, pp. 115-129 Jamison, B., Olariu, S., A linear time algorithm to recognize P4-reducible graphs (1995) Theoret. Comput. Sci., 145, pp. 329-344 Kaplan, H., Shamir, R., Bounded degree interval sandwich problems (1999) Algorithmica, 24 (2), pp. 96-104 Kaplan, H., Shamir, R., Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques (1996) SIAM J. Comput., 25, pp. 540-561 H. Lerchs, On cliques and kernels, Tech. Report Dept. of Comput. Sci., University of Toronto, 1971McConnell, R.M., Spinrad, J.P., Modular decomposition and transitive orientation (1999) Discrete Math., 201, pp. 189-241 Sritharan, R., Chordal bipartite completion of colored graphs Discrete Math, , submitted for publication Tarjan, R.E., Depth-first search and linear graph algorithms (1972) SIAM J. Comput., 1, pp. 146-160 Teixeira, R.B., Figueiredo, C.M.H., The sandwich problem for cutsets: clique cutset, k-star cutset (2006) Discrete Appl. Math., 154, pp. 1791-1798 Yannakakis, M., Computing the minimum fill-in is NP-complete (1981) SIAM J. Alg. Discrete Meth., 2, pp. 77-79