On Independence Domination

详细信息    查看全文

• 作者：Wing-Kai Hon (18)
  Ton Kloks (18)
  Hsiang-Hsuan Liu (18)
  Sheung-Hung Poon (18)
  Yue-Li Wang (19)
  
• 关键词：Independence domination ; Domination ; Cograph ; Distance ; hereditary graph ; Permutation graph ; Exact algorithm
• 刊名：Lecture Notes in Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：8070
• 期：1
• 页码：195-209
• 全文大小：251KB
• 参考文献：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.