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:
Unifying Duality Theorems for Width Parameters in Graphs and Matroids (Extended Abstract) Kapitel lesen Erstes Kapitel lesen

2014 | OriginalPaper | Buchkapitel

Polynomial Time Recognition of Squares of Ptolemaic Graphs and 3-sun-free Split Graphs

verfasst von : Van Bang Le, Andrea Oversberg, Oliver Schaudt

Erschienen in: Graph-Theoretic Concepts in Computer Science

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The square of a graph \(G\), denoted \(G^2\), is obtained from \(G\) by putting an edge between two distinct vertices whenever their distance is two. Then \(G\) is called a square root of \(G^2\). Deciding whether a given graph has a square root is known to be NP-complete, even if the root is required to be a chordal graph or even a split graph.
We present a polynomial time algorithm that decides whether a given graph has a ptolemaic square root. If such a root exists, our algorithm computes one with a minimum number of edges.
In the second part of our paper, we give a characterization of the graphs that admit a 3-sun-free split square root. This characterization yields a polynomial time algorithm to decide whether a given graph has such a root, and if so, to compute one.

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 Parameterized Edge Hamiltonicity
Nächstes Kapitel The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
Literatur
1.
2.
Adamszek, A., Adamszek, M.: Uniqueness of graph square roots of girth six. Electron. J. Combin. 18, 139 (2011)MathSciNet
3.
4.
5.
Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM, Philadelphia (1999)CrossRefMATH
6.
Chang, M.-S., Ko, M.-T., Lu, H.-I.: Linear-time algorithms for tree root problems. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol. 4059, pp. 411–422. Springer, Heidelberg (2006)CrossRef
7.
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
8.
Dalhaus, E., Duchet, P.: On strongly chordal graphs. Ars Combin. 24B, 23–30 (1987)
9.
Dourado, M.C., Protti, F., Szwarcfiter, J.L.: Complexity aspects of the helly property: graphs and hypergraphs. Electron. J. Combin. 17, 1–53 (2009)CrossRef
10.
11.
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
12.
13.
14.
15.
Lau, L.C., Corneil, D.G.: Recognizing powers of proper interval, split, and chordal graphs. SIAM J. Discrete Math. 18, 83–102 (2004)MathSciNetCrossRefMATH
16.
Le, V.B., Nguyen, N.T.: Hardness results and efficient algorithms for graph powers. In: Paul, C., Habib, M. (eds.) WG 2009. LNCS, vol. 5911, pp. 238–249. Springer, Heidelberg (2010)CrossRef
17.
18.
Le, V.B., Tuy, N.N.: A good characterization of squares of strongly chordal split graphs. Inf. Process. Lett. 310, 120–123 (2011)MathSciNetCrossRef
19.
20.
Milanič, M., Schaudt, O.: Computing square roots of trivially perfect and threshold graphs. Disc. App. Math. 161, 1538–1545 (2013)CrossRefMATH
21.
22.
Prisner, E.: Hereditary clique-Helly graphs. J. Comb. Math. Comb. Comput. 14, 216–220 (1993)MathSciNetMATH
23.
Raychaudhuri, A.: On powers of strongly chordal and circular arc graphs. Ars Combin. 34, 147–160 (1992)MathSciNetMATH
24.
Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6, 505–517 (1977)MathSciNetCrossRefMATH
Metadaten
Titel
Polynomial Time Recognition of Squares of Ptolemaic Graphs and 3-sun-free Split Graphs
verfasst von
Van Bang Le
Andrea Oversberg
Oliver Schaudt
Copyright-Jahr
2014
Buch
Graph-Theoretic Concepts in Computer Science

Print ISBN: 978-3-319-12339-4

Electronic ISBN: 978-3-319-12340-0

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-3-319-12340-0_30