×

zbMATH — the first resource for mathematics

Complexity classification of some edge modification problems. (English) Zbl 0982.68104
This is the complete version of the paper appeared in Lect. Notes Comput. Sci. 1665, 65-77 (1999; Zbl 0952.68112).

MSC:
68R10 Graph theory (including graph drawing) in computer science
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agrawal, A.; Klein, P.; Ravi, R., Cutting down on fill using nested dissection: provably good elimination orderings, (), 31-55 · Zbl 0803.68082
[2] Asano, T., An application of duality to edge-deletion problems, SIAM J. comput., 16, 2, 312-331, (1987) · Zbl 0634.68033
[3] T. Asano, T. Hirata, Edge-deletion and edge-contraction problems, Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, San Francisco, California, 1982, pp. 245-254.
[4] A. Ben-Dor, private communication, 1996.
[5] Bodlaender, H.; de Fluiter, B., On intervalizing k-colored graphs for DNA physical mapping, Discrete appl. math., 71, 55-77, (1996) · Zbl 0867.92008
[6] B. Bollobás, Random Graphs, Academic Press, New York, 1985, (Chapter XII).
[7] Brandstädt, A.; Le, V.B.; Spinrad, J.P., Graph classes – a survey, SIAM monographs in discrete mathematics and applications, (1999), SIAM Philadelphia
[8] Cai, L., Fixed-parameter tractability of graph modification problems for hereditary properties, Inform. process. lett., 58, 171-176, (1996) · Zbl 0875.68702
[9] K. Cirino, S. Muthukrishnan, N. Narayanaswamy, H. Ramesh, Graph editing to bipartite interval graphs: exact and asymptotic bounds, Technical Report, Bell Laboratories Innovations, Lucent Technologies, 1996.
[10] Corneil, D.G.; Olariu, S.; Stewart, L., Asteroidal triple-free graphs, SIAM. J. discrete math., 10, 3, 399-430, (1997) · Zbl 0884.05075
[11] El-Mallah, E.S.; Colbourn, C.J., The complexity of some edge deletion problems, IEEE trans. circuits systems, 35, 3, 354-362, (1988) · Zbl 0654.68084
[12] M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Co., San Francisco, 1979. · Zbl 0411.68039
[13] Garey, M.R.; Johnson, D.S.; Stockmeyer, L., Some simplified, NP-complete problems, theoret. comput. sci., 1, 237-267, (1976) · Zbl 0338.05120
[14] Goldberg, P.W.; Golumbic, M.C.; Kaplan, H.; Shamir, R., Four strikes against physical mapping of DNA, J. comput. biol., 2, 1, 139-152, (1995)
[15] Golumbic, M.; Kaplan, H.; Shamir, R., Graph sandwich problems, J. algorithms, 19, 449-473, (1995) · Zbl 0838.68054
[16] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[17] Golumbic, M.C.; Kaplan, H.; Shamir, R., On the complexity of DNA physical mapping, Adv. appl. math., 15, 251-261, (1994) · Zbl 0806.92007
[18] Golumbic, M.C.; Shamir, R., Complexity and algorithms for reasoning about time: A graph-theoretic approach, J. ACM, 40, 1108-1133, (1993) · Zbl 0795.68095
[19] Hakimi, S.L.; Schmeichel, E.F.; Young, N.E., Orienting graphs to optimize reachability, Inform. process. lett., 63, 5, 229-235, (1997) · Zbl 1337.68130
[20] Hammer, P.L.; Ibaraki, T.; Peled, U.N., Threshold numbers and threshold completions, (), 125-145 · Zbl 0482.05060
[21] Hammer, P.L.; Simeone, B., The splittance of a graph, Combinatorica, 1, 275-284, (1981) · Zbl 0492.05043
[22] J. Håstad, Some optimal inapproximability results, Proceedings of 29th STOC, 1997, pp. 1-10, full version: E-CCC Report number TR97-037. · Zbl 0963.68193
[23] Kaplan, H.; Shamir, R., Bounded degree interval sandwich problems, Algorithmica, 24, 96-104, (1999) · Zbl 0934.68070
[24] Kaplan, H.; Shamir, R.; Tarjan, R.E., Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs, SIAM J. comput., 28, 1906-1922, (1999) · Zbl 0928.68124
[25] T. Kashiwabara, T. Fujisawa, An NP-complete problem on interval graphs, IEEE International Symposium on Circuits and Systems (12th), 1979, pp. 82-83.
[26] Lewis, J.; Yannakakis, M., The node deletion problem for hereditary properties is NP-complete, J. comput. systems sci., 20, 219-230, (1980) · Zbl 0436.68029
[27] Lovás, L., A characterization of perfect graphs, J. combin. theory, 95-98, (1972)
[28] Lund, C.; Yannakakis, M., The approximation of maximum subgraph problems, (), 40-51 · Zbl 1422.68087
[29] Mahadev, N.; Peled, U., Threshold graphs and related topics, Annals of discrete mathematics, 49, 299-308, (1994)
[30] F. Margot, Some complexity results about threshold graphs, Discrete Appl. Math. 49. · Zbl 0802.90109
[31] A. Natanzon, Complexity and approximation of some graph modification problems, Master’s Thesis, Department of Computer Science, Tel Aviv University, 1999.
[32] A. Natanzon, R. Shamir, R. Sharan, A polynomial approximation algorithm for the minimum fill-in problem, SIAM J. Comput. 30 (2000) 1067-1079. A preliminary version appeared in: Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC’98), ACM Press, New York, 1998, pp. 41-47. · Zbl 0969.68194
[33] A. Natanzon, R. Shamir, R. Sharan, Complexity classification of some edge modification problems, Proceedings of 25th International Workshop (WG ’99), Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 1665, Springer, Berlin, 1999, pp. 65-77. · Zbl 0952.68112
[34] R. Ravi, A. Agrawal, P. Klein, Ordering problems approximated: single processor scheduling and interval graph completion, Proceedings of ICALP 1991, Lecture Notes in Computer Science, Vol. 510, Springer, Berlin, 1991, pp. 751-762. · Zbl 0772.68043
[35] Rose, J.D., A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, (), 183-217
[36] R. Shamir, R. Sharan, Cluster graph modification problems, manuscript, Tel-Aviv University, 2000. · Zbl 1022.68104
[37] Tarjan, R.E.; Yannakakis, M., Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. comput., 13, 566-579, (1984) · Zbl 0545.68062
[38] L. Trevisan, G. Sorkin, M. Sudan, D. Williamson, Gadgets, approximation, and linear programming, Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS’96), 1996, pp. 617-626. · Zbl 0957.68048
[39] J. Xue, Edge-maximal triangulated subgraph and heuristics for the maximum clique problem, Technical report, Graduate School of Management, Clark University, Worcester, MA, July 1993.
[40] Yannakakis, M., Edge deletion problems, SIAM J. comput., 10, 2, 297-309, (1981) · Zbl 0468.05043
[41] Yannakakis, M., Computing the minimum fill-in is NP-complete, SIAM J. algebrac discrete methods, 2, 77-79, (1981) · Zbl 0496.68033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.