Home > Information Control Problems in Manufacturing > 13th IFAC Symposium on Information Control Problems in Manufacturing > On the Complexity of Dissociation Set Problems in Graphs
» Download Article
Document
Reference
On the Complexity of Dissociation Set Problems in Graphs
Information Control Problems in Manufacturing, Volume # 13 | Part# 1
Location: V.A. Trapeznikov Institute of Control Sciences, Russia
National Organizing Committee Chair: Bakhtadze, Natalia,
Dozortsev, Victor
International Program Committee Chair: Dolgui, Alexandre,
Pereira, Carlos Eduardo,
Mirkin, Evgeny A. ,
Kostyukov, Valentin E.
Conference Editor: Bakhtadze, Natalia,
Dolgui, Alexandre
Authors
Orlovich, Yuri; Dolgui, Alexandre; Finke, Gerd; Gordon, Valery; Werner, Frank
Digital Object Identifier (DOI)
10.3182/20090603-3-RU-2001.00170
Page Numbers:
1032-1036
Index Terms
Computational Science; Discrete Applied Mathematics; Graph theory
Abstract
A subset of vertices in a graph is called a dissociation set if it induces a subgraph with vertex degree at most 1. A dissociation set D is maximal if no other dissociation set contains D. The complexity of finding a dissociation set of maximum size in line graphs and finding a maximal dissociation set of minimum size in general graphs is considered.
References
REFERENCES Alekseev, V.E. (2004). Polynomial algorithm for finding the largest independent sets in graphs without forks. Discrete Applied Mathematics, 135, 3–16. Boliac, R., Cameron, K., and Lozin, V. (2004). On computing the dissociation number and the induced matching number of bipartite graphs. Ars Combinatoria, 72, 241–253. Brandstädt, A., Le, V.B., and Spinrad, J.P. (1999). Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, PA. Garey, M.R. and Johnson, D.S. (1979). Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman and Co., San Francisco, CA. Golumbic, M.C. and Lewenstein, M. (2000). New results on induced matchings. Discrete Applied Mathematics, 101, 157–165. Harary, F. and Holzmann, C. (1974). Line graphs of bipartite graphs. Review of the Society of Mathematics of Chile, 1, 19–20. Haynes, T.W., Hedetniemi, S.T., and Slater, P.J. (1998). Fundamentals of Domination in Graphs. Marcel Dekker, Inc., New York, NY. Kirkpatrick, D.G. and Hell, P. (1978). On the complexity of a generalized matching problem. Proceedings of the 10th Annual ACM Symposium on Theory of Computing. ACM, New York, 240–245. Lozin, V. and Milanic, M. (2008). A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. Journal of Discrete Algorithms, 6, 595–604. Lozin, V. and Rautenbach, D. (2003). Some results on graphs without long induced paths. Information Processing Letters, 88, 167–171. Orlovich, Yu., Finke, G., Gordon, V., and Zverovich, I. (2008). Approximability results for the maximum and minimum maximal induced matching problems. Discrete Optimization, 5, 584–593. Papadimitriou, C.H. and Yannakakis, M. (1982). The complexity of restricted spanning tree problems. Journal of the ACM, 29, 285–309. Yannakakis, M. (1981). Node-deletion problems on bipartite graphs. SIAM Journal of Computing, 10, 310– 327.