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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
On the Complexity of Computing Treebreadth Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Finding Cactus Roots in Polynomial Time

verfasst von : Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, Anthony Stewart

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

A cactus is a connected graph in which each edge belongs to at most one cycle. A graph H is a cactus root of a graph G if H is a cactus and G can be obtained from H by adding an edge between any two vertices in H that are of distance 2 in H. We show that it is possible to test in \(O(n^4)\) time whether an n-vertex graph G has a cactus root.

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 Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs
Nächstes Kapitel Computing Giant Graph Diameters
Literatur
1.
Adamaszek, A., Adamaszek, M.: Uniqueness of graph square roots of girth six. Electron. J. Comb. 18, #P139 (2011)
2.
Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 305–1317 (1996)MathSciNetCrossRefMATH
3.
Cochefert, M., Couturier, J.-F., Golovach, P.A., Kratsch, D., Paulusma, D.: Sparse square roots. In: Brandstädt, A., Jansen, K., Reischuk, R. (eds.) WG 2013. LNCS, vol. 8165, pp. 177–188. Springer, Heidelberg (2013)CrossRef
4.
Cochefert, M., Couturier, J., Golovach, P.A., Kratsch, D., Paulusma, D.: Parameterized algorithms for finding square roots. Algorithmica 74, 602–629 (2016)MathSciNetCrossRefMATH
5.
Courcelle, B.: The monadic second-order logic of graphs III: tree-decompositions, minor and complexity issues. ITA 26, 257–286 (1992)MathSciNetMATH
6.
Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Switzerland (2015)CrossRefMATH
7.
Diestel, R.: Graph Theory, 4th edn. Graduate Texts in Mathematics, vol. 173. Springer, Heidelberg (2012)
8.
Farzad, B., Karimi, M.: Square-root finding problem in graphs, a complete dichotomy theorem. CoRR, abs/1210.7684 (2012)
9.
Farzad, B., Lau, L.C., Le, V.B., Tuy, N.N.: Complexity of finding graph roots with girth conditions. Algorithmica 62, 38–53 (2012)MathSciNetCrossRefMATH
10.
Golovach, P.A., Kratsch, D., Paulusma, D., Stewart, A.: A linear kernel for finding square roots of almost planar graphs. In: Proceedings of SWAT 2016, Leibniz International Proceedings in Informatics (2016, to appear)
11.
Golovach, P.A., Kratsch, D., Paulusma, D., Stewart, A.: Squares of low clique number. In: Proceedings of CTW 2016, Electronic Notes in Discrete Mathematics (2016, to appear)
12.
13.
Lau, L.C., Corneil, D.G.: Recognizing powers of proper interval, split, and chordal graphs. SIAM J. Discrete Math. 18, 83–102 (2004)MathSciNetCrossRefMATH
14.
Le, V.B., Oversberg, A., Schaudt, O.: Polynomial time recognition of squares of ptolemaic graphs and 3-sun-free split graphs. Theor. Comput. Sci. 602, 39–49 (2015)MathSciNetCrossRefMATH
15.
Le, V.B., Oversberg, A., Schaudt, O.: A unified approach for recognizing squares of split graphs. Manuscript (2015)
16.
17.
Le, V.B., Tuy, N.N.: A good characterization of squares of strongly chordal split graphs. Inf. Process. Lett. 111, 120–123 (2011)MathSciNetCrossRefMATH
18.
19.
Milanic, M., Oversberg, A., Schaudt, O.: A characterization of line graphs that are squares of graphs. Discrete Appl. Math. 173, 83–91 (2014)MathSciNetCrossRefMATH
20.
Milanic, M., Schaudt, O.: Computing square roots of trivially perfect and threshold graphs. Discrete Appl. Math. 161, 1538–1545 (2013)MathSciNetCrossRefMATH
21.
22.
23.
24.
Metadaten
Titel
Finding Cactus Roots in Polynomial Time
verfasst von
Petr A. Golovach
Dieter Kratsch
Daniël Paulusma
Anthony Stewart
Copyright-Jahr
2016
Buch
Combinatorial Algorithms

Print ISBN: 978-3-319-44542-7

Electronic ISBN: 978-3-319-44543-4

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-44543-4_28