Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Counting Graphs and Null Models of Complex Networks: Configuration Model and Extensions Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Enumeration and Maximum Number of Maximal Irredundant Sets for Chordal Graphs

Authors : Petr A. Golovach, Dieter Kratsch, Mathieu Liedloff, Mohamed Yosri Sayadi

Published in: Graph-Theoretic Concepts in Computer Science

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper we provide exponential-time algorithms to enumerate the maximal irredundant sets of chordal graphs and two of their subclasses. We show that the maximum number of maximal irredundant sets of a chordal graph is at most \(1.7549^n\), and these can be enumerated in time \(O(1.7549^n)\). For interval graphs, we achieve the better upper bound of \(1.6957^n\) for the number of maximal irredundant sets and we show that they can be enumerated in time \(O(1.6957^n)\). Finally, we show that forests have at most \(1.6181^n\) maximal irredundant sets that can be enumerated in time \(O(1.6181^n)\). We complement the latter result by providing a family of forests having at least \(1.5292^n\) maximal irredundant sets.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2
next chapter The Minimum Conflict-Free Row Split Problem Revisited
Literature
1.
Abu-Khzam, F.N., Heggernes, P.: Enumerating minimal dominating sets in chordal graphs. Inf. Process. Lett. 116(12), 739–743 (2016)CrossRefMathSciNetMATH
2.
Bertossi, A.A., Gori, A.: Total domination and irredundance in weighted interval graphs. SIAM J. Discrete Math. 1(3), 317–327 (1988)CrossRefMathSciNetMATH
3.
Binkele-Raible, D., Brankovic, L., Cygan, M., Fernau, H., Kneis, J., Kratsch, D., Langer, A., Liedloff, M., Pilipczuk, M., Rossmanith, P., Wojtaszczyk, J.O.: Breaking the \(2^{\rm {n}}\)-barrier for irredundance: two lines of attack. J. Discrete Algorithms 9(3), 214–230 (2011)CrossRefMathSciNetMATH
4.
Bodlaender, H., Boros, E., Heggernes, P., Kratsch, D.: Open problems of the Lorentz workshop, “Enumeration Algorithms using Structure”. Technical report Series UU-CS-2015-016, Utrecht University (2016)
5.
Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey. In: SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1999)
6.
Cockayne, E.J., Favaron, O., Payan, C., Thomason, A.G.: Contributions to the theory of domination, independence and irredundance in graphs. Discrete Math. 33(3), 249–258 (1981)CrossRefMathSciNetMATH
7.
Couturier, J., Heggernes, P., van’t Hof, P., Kratsch, D.: Minimal dominating sets in graph classes: combinatorial bounds and enumeration. Theor. Comput. Sci. 487, 82–94 (2013)CrossRefMathSciNetMATH
8.
Couturier, J., Letourneur, R., Liedloff, M.: On the number of minimal dominating sets on some graph classes. Theor. Comput. Sci. 562, 634–642 (2015)CrossRefMathSciNetMATH
9.
10.
Downey, R.G., Fellows, M.R., Raman, V.: The complexity of irredundant sets parameterized by size. Discrete Appl. Math. 100(3), 155–167 (2000)CrossRefMathSciNetMATH
11.
Eiter, T., Gottlob, G.: Identifying the minimal transversals of a hypergraph and related problems. SIAM J. Comput. 24(6), 1278–1304 (1995)CrossRefMathSciNetMATH
12.
13.
Fomin, F.V., Grandoni, F., Pyatkin, A.V., Stepanov, A.A.: Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications. ACM Trans. Algorithms 5(1), 9 (2008)CrossRefMathSciNet
14.
15.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)MATH
16.
Golovach, P.A., Heggernes, P., Kratsch, D.: Enumeration and maximum number of minimal connected vertex covers in graphs. In: Lipták, Z., Smyth, W.F. (eds.) IWOCA 2015. LNCS, vol. 9538, pp. 235–247. Springer, Cham (2016). doi:10.​1007/​978-3-319-29516-9_​20 CrossRef
17.
Golovach, P.A., Kratsch, D., Liedloff, M., Rao, M., Sayadi, M.Y.: On maximal irredundant sets and \((\sigma , \varrho )\)-dominating sets in paths. Manuscript (2016)
18.
Golovach, P.A., Kratsch, D., Sayadi, M.Y.: Enumeration of maximal irredundant sets for claw-free graphs. In: Fotakis, D., Pagourtzis, A., Paschos, V.T. (eds.) CIAC 2017. LNCS, vol. 10236, pp. 297–309. Springer, Cham (2017). doi:10.​1007/​978-3-319-57586-5_​25 CrossRef
19.
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, vol. 57, 2nd edn. Elsevier Science B.V., Amsterdam (2004)
20.
Habib, M., McConnell, R.M., Paul, C., Viennot, L.: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theor. Comput. Sci. 234(1–2), 59–84 (2000)CrossRefMathSciNetMATH
21.
Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Domination in Graphs: Advanced Topics. Marcel Dekker Inc., New York (1998)MATH
22.
Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs, Monographs and Textbooks in Pure and Applied Mathematics, vol. 208. Marcel Dekker Inc., New York (1998)
23.
Hedetniemi, S.T., Laskar, R., Pfaff, J.: Irredundance in graphs: a survey. In: Proceedings of the Sixteenth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Boca Raton, FL, vol. 48, pp. 183–193 (1985)
24.
Jacobson, M.S., Peters, K.: Chordal graphs and upper irredundance, upper domination and independence. Discrete Math 86(1–3), 59–69 (1990)CrossRefMathSciNetMATH
25.
Kanté, M.M., Limouzy, V., Mary, A., Nourine, L.: On the enumeration of minimal dominating sets and related notions. SIAM J. Discrete Math. 28(4), 1916–1929 (2014)CrossRefMathSciNetMATH
26.
Khachiyan, L., Boros, E., Elbassioni, K.M., Gurvich, V.: On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs. Theor. Comput. Sci. 382(2), 139–150 (2007)CrossRefMathSciNetMATH
27.
Korte, N., Möhring, R.H.: An incremental linear-time algorithm for recognizing interval graphs. SIAM J. Comput. 18(1), 68–81 (1989)CrossRefMathSciNetMATH
28.
Lekkerkerker, C.G., Boland, J.C.: Representation of a finite graph by a set of intervals on the real line. Fund. Math. 51, 45–64 (1962/1963)
Metadata
Title
Enumeration and Maximum Number of Maximal Irredundant Sets for Chordal Graphs
Authors
Petr A. Golovach
Dieter Kratsch
Mathieu Liedloff
Mohamed Yosri Sayadi
Copyright Year
2017
Book
Graph-Theoretic Concepts in Computer Science

Print ISBN: 978-3-319-68704-9

Electronic ISBN: 978-3-319-68705-6

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-68705-6_22

Premium Partner

    Image Credits