Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Speeding Up Cover Time of Sparse Graphs Using Local Knowledge Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs

verfasst von : Petr A. Golovach, Pinar Heggernes, Dieter Kratsch

Erschienen in: Combinatorial Algorithms

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Connected Vertex Cover is one of the classical problems of computer science, already mentioned in the monograph of Garey and Johnson [15]. Although the optimization and decision variants of finding connected vertex covers of minimum size or weight are well studied, surprisingly there is no work on the enumeration or maximum number of minimal connected vertex covers of a graph. In this paper we show that the maximum number of minimal connected vertex covers of a graph is \(O(1.8668^n)\), and these can be enumerated in time \(O(1.8668^n)\). For graphs of chordality at most 5, we are able to give a better upper bound, and for chordal graphs and distance-hereditary graphs we are able to give tight bounds on the maximum number of minimal connected vertex covers.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel How to Design Graphs with Low Forwarding Index and Limited Number of Edges
Nächstes Kapitel Fast Multiple Order-Preserving Matching Algorithms
Fußnoten
1
The computations have been done by computer.
 
Literatur
1.
2.
Basavaraju, M., Heggernes, P., van’t Hof, P., Saei, R., Villanger, Y.: Maximal induced matchings in triangle-free graphs. In: Kratsch, D., Todinca, I. (eds.) WG 2014. LNCS, vol. 8747, pp. 93–104. Springer, Heidelberg (2014)
3.
Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey. SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (1999)
4.
Byskov, J.M.: Enumerating maximal independent sets with applications to graph colouring. Oper. Res. Lett. 32(6), 547–556 (2004)CrossRefMathSciNetMATH
5.
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
6.
Couturier, J.-F., Heggernes, P., van’t Hof, P., Villanger, Y.: Maximum number of minimal feedback vertex sets in chordal graphs and cographs. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol. 7434, pp. 133–144. Springer, Heidelberg (2012)CrossRef
7.
Cygan, M.: Deterministic parameterized connected vertex cover. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. 7357, pp. 95–106. Springer, Heidelberg (2012)CrossRef
8.
D’Atri, A., Moscarini, M.: Distance-hereditary graphs, steiner trees, and connected domination. SIAM J. Comput. 17(3), 521–538 (1988)CrossRefMathSciNet
9.
Escoffier, B., Gourvès, L., Monnot, J.: Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs. J. Discrete Algorithms 8(1), 36–49 (2010)CrossRefMathSciNetMATH
10.
Fomin, F.V., Gaspers, S., Pyatkin, A.V., Razgon, I.: On the minimum feedback vertex set problem: exact and enumeration algorithms. Algorithmica 52(2), 293–307 (2008)CrossRefMathSciNetMATH
11.
Fomin, F.V., Heggernes, P., Kratsch, D.: Exact algorithms for graph homomorphisms. Theor. Comp. Syst. 41(2), 381–393 (2007)CrossRefMathSciNetMATH
12.
Fomin, F.V., Heggernes, P., Kratsch, D., Papadopoulos, C., Villanger, Y.: Enumerating minimal subset feedback vertex sets. Algorithmica 69(1), 216–231 (2014)CrossRefMathSciNetMATH
13.
Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2010)CrossRefMATH
14.
Fomin, F.V., Villanger, Y.: Finding induced subgraphs via minimal triangulations. In: 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, pp. 383–394 (2010)
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.
17.
Golovach, P.A., Heggernes, P., Kratsch, D., Saei, R.: Subset feedback vertex sets in chordal graphs. J. Discrete Algorithms 26, 7–15 (2014)CrossRefMathSciNetMATH
18.
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, vol. 57, 2nd edn. Elsevier Science B.V., Amsterdam (2004)
19.
Hujtera, M., Tuza, Z.: The number of maximal independent sets in triangle-free graphs. SIAM J. Discrete Math. 6(2), 284–288 (1993)CrossRefMathSciNet
20.
Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: On generating all maximal independent sets. Inf. Process. Lett. 27(3), 119–123 (1988)CrossRefMathSciNetMATH
21.
22.
Miller, R.E., Muller, D.: A problem of maximum consistent subsets. IBM Research Rep. RC-240. J. T. Watson Research Center, Yorktown Heights, New York, USA (1960)
23.
24.
Pelsmajer, M.J., Tokazy, J., West, D.B.: New proofs for strongly chordal graphs and chordal bipartite graphs (2004). Unpublished manuscript
25.
Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6(3), 505–517 (1977)CrossRefMathSciNetMATH
Metadaten
Titel
Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs
verfasst von
Petr A. Golovach
Pinar Heggernes
Dieter Kratsch
Copyright-Jahr
2016
Buch
Combinatorial Algorithms

Print ISBN: 978-3-319-29515-2

Electronic ISBN: 978-3-319-29516-9

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-29516-9_20

Premium Partner

    Bildnachweise