参考文献:1. Aharoni, R., Berger, E., Ziv, R.: A tree version of K?nig’s theorem. Combinatorica?22, 335-43 (2002) CrossRef 2. Aharoni, R., Szabó, T.: Vizing’s conjecture for chordal graphs. Discrete Mathematics?309, 1766-768 (2009) CrossRef 3. Baker, B.: Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM?41, 153-80 (1994) CrossRef 4. Baker, K., Fishburn, P., Roberts, F.: Partial orders of dimension 2. Networks?2, 11-8 (1971) CrossRef 5. Bertossi, A.: Dominating sets for split and bipartite graphs. Information Processing Letters?19, 37-0 (1984) CrossRef 6. Bodlaender, H.: A partial / k-arboretum of graphs with bounded treewidth. Theoretical Computer Science?209, 1-5 (1998) CrossRef 7. Booth, K., Johnson, J.: Domination in chordal graphs. SIAM Journal on Computing?11, 191-99 (1982) CrossRef 8. Corneil, D., Lerchs, H., Stewart-Burlingham, L.: Complement reducible graphs. Discrete Applied Mathematics?3, 163-74 (1981) CrossRef 9. Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation?85, 12-5 (1990) CrossRef 10. Cygan, M., Pilipczuk, M., Pilipczuk, M.: Known algorithms for edge clique cover are probably optimal. Manuscript on ArXiV: 1203.1754v1 (2012) 11. Damiand, G., Habib, M., Paul, C.: A simple paradigm for graph recognition: application to cographs and distance hereditary graphs. Theoretical Computer Science?263, 99-11 (2001) CrossRef 12. Domke, G., Fisher, D., Ryan, J., Majumdar, A.: Fractional domination of strong direct products. Discrete Applied Mathematics?50, 89-1 (1994) CrossRef 13. Farber, M.: Domination, independent domination, and duality in strongly chordal graphs. Discrete Applied Mathematics?7, 115-36 (1984) CrossRef 14. Fisher, D.: Domination, fractional domination, 2-packings, and graph products. SIAM Journal on Discrete Mathematics?7, 493-98 (1984) CrossRef 15. Fomin, F., Kratsch, D.: Exact exponential algorithms. EATCS series, Texts in Theoretical Computer Science. Springer (2010) 16. Golumbic, M.: Algorithmic graph theory and perfect graphs. Annals of Discrete Mathematics, vol.?57. Elsevier (2004) 17. Gregory, D., Pullman, N.: On a clique covering problem of Orlin. Discrete Mathematics?41, 97-9 (1982) CrossRef 18. Gr?tschel, M., Lovász, L., Schrijver, A.: Relaxations of vertex packing. Journal of Combinatorial Theory, Series B?40, 330-43 (1986) CrossRef 19. Halin, R.: / S-functions for graphs. Journal of Geometry?8, 171-86 (1976) CrossRef 20. Hammack, R., Imrich, W., Klavzar, S.: Handbook of Product Graphs. CRC Press (2011) 21. Howorka, E.: A characterization of distance-hereditary graphs. The Quarterly Journal of Mathematics?28, 417-20 (1977) CrossRef 22. Imrich, W., Klav?ar, S.: Product graphs: structure and recognition. John Wiley & Sons, New York (2000) 23. Kloks, T.: Treewidth -Computations and Approximations. LNCS, vol.?842. Springer (1994) 24. Hung, L.-J., Kloks, T.: On some simple widths. In: Rahman, M. S., Fujita, S. (eds.) WALCOM 2010. LNCS, vol.?5942, pp. 204-15. Springer, Heidelberg (2010) CrossRef 25. Kloks, T., Liu, C., Poon, S.: On edge-independent sets (2013) (manuscript) 26. Kloks, T., Wang, Y.: Advances in graph algorithms (2013) (Manuscript) 27. Lichtenstein, D.: Planar formulae and their uses. SIAM Journal on Computing?11, 329-43 (1982) CrossRef 28. Lovász, L.: On the Shannon capacity of a graph. IEEE Transactions on Information Theory?IT-25, 1- (1979) 29. Milani?, M.: A note on domination and independence-domination numbers of graphs. Ars Mathematica Contemporanea?6, 89-7 (2013) 30. Moon, J., Moser, L.: On cliques in graphs. Israel Journal of Mathematics?3, 23-8 (1965) CrossRef 31. Oum, S.: Graphs of bounded rank-width, PhD Thesis, Princeton University (2005) 32. Scheinerman, E., Ullman, D.: Fractional graph theory. Wiley–Interscience, New York (1997) 33. Suen, S., Tarr, J.: An improved inequality related to Vizing’s conjecture. The Electronic Journal of Combinatorics?19, 8 (2012) 34. Tedder, M., Corneil, D., Habib, M., Paul, C.: Simpler linear-time modular decomposition via recursive factorizing permutations. Manuscript on ArXiv: 0710.3901 (2008) 35. Telle, J.: Vertex partitioning problems: characterization, complexity and algorithms on partial / k-trees, PhD Thesis, University of Oregon (1994) 36. Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM Journal on Computing?6, 505-17 (1977) CrossRef 37. Vizing, V.: Cartesian product of graphs. Vychisl. Sistemy, 209-12 (1963) (Russian) 38. Vizing, V.: Some unsolved problems in graph theory. Uspehi Mat. Nauk?23, 117-34 (1968) (Russian)
作者单位:Wing-Kai Hon (18) Ton Kloks (18) Hsiang-Hsuan Liu (18) Sheung-Hung Poon (18) Yue-Li Wang (19)
18. National Tsing Hua University, Taiwan 19. National Taiwan University of Science and Technology, Taiwan
文摘
Let G be a graph. The independence-domination number γ i (G) is the maximum over all independent sets I in G of the minimal number of vertices needed to dominate I. In this paper we investigate the computational complexity of γ i (G) for graphs in several graph classes related to cographs. We present an exact exponential algorithm. We show that there is a polynomial-time algorithm to compute a maximum independent set in the Cartesian product of two cographs. We prove that independence domination is NP-hard for planar graphs and we present a PTAS.