Skip to main content

2015 | OriginalPaper | Buchkapitel

Trees, Paths, Stars, Caterpillars and Spiders

verfasst von : Minghui Jiang

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

For any \(k \ge 2\), deciding whether the linear arboricity, star arboricity, caterpillar arboricity, and spider arboricity, respectively, of a bipartite graph are at most k are all NP-complete.

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!

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!

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!

Literatur
1.
Zurück zum Zitat Akiyama, J., Exoo, G., Harary, F.: Covering and packing in graphs III: cyclic and acyclic invariants. Math. Slovoca 30, 405–417 (1980)MathSciNetMATH Akiyama, J., Exoo, G., Harary, F.: Covering and packing in graphs III: cyclic and acyclic invariants. Math. Slovoca 30, 405–417 (1980)MathSciNetMATH
3.
Zurück zum Zitat Cygan, M., Hou, J., Kowalik, Ł., Lužar, B., Wu, J.: A planar linear arboricity conjecture. J. Graph Theor. 69, 403–425 (2012)MathSciNetCrossRefMATH Cygan, M., Hou, J., Kowalik, Ł., Lužar, B., Wu, J.: A planar linear arboricity conjecture. J. Graph Theor. 69, 403–425 (2012)MathSciNetCrossRefMATH
4.
Zurück zum Zitat Fiala, J., Jansen, K., Le, V.B., Seidel, E.: Graph subcolorings: complexity and algorithms. SIAM J. Discrete Math. 16, 635–650 (2003)MathSciNetCrossRefMATH Fiala, J., Jansen, K., Le, V.B., Seidel, E.: Graph subcolorings: complexity and algorithms. SIAM J. Discrete Math. 16, 635–650 (2003)MathSciNetCrossRefMATH
5.
Zurück zum Zitat Gabow, H.N., Westermann, H.H.: Forests, frames, and games: algorithms for matroid sums and applications. Algorithmica 7, 465–497 (1992)MathSciNetCrossRefMATH Gabow, H.N., Westermann, H.H.: Forests, frames, and games: algorithms for matroid sums and applications. Algorithmica 7, 465–497 (1992)MathSciNetCrossRefMATH
11.
Zurück zum Zitat Klein, P., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. Algorithms 19, 104–115 (1995)MathSciNetCrossRefMATH Klein, P., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. Algorithms 19, 104–115 (1995)MathSciNetCrossRefMATH
12.
Zurück zum Zitat Lovász, L.: Coverings and colorings of hypergraphs. In: Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, pp. 3–12. Utilitas Mathematica Publishing, Winnipeg (1973) Lovász, L.: Coverings and colorings of hypergraphs. In: Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, pp. 3–12. Utilitas Mathematica Publishing, Winnipeg (1973)
13.
Zurück zum Zitat Maffray, F., Preissmann, M.: On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs. Discrete Math. 162, 313–317 (1996)MathSciNetCrossRefMATH Maffray, F., Preissmann, M.: On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs. Discrete Math. 162, 313–317 (1996)MathSciNetCrossRefMATH
15.
Zurück zum Zitat Peroche, B.: Complexité de l’arboricité linéaire d’un graphe. RAIRO Recherche Operationelle 16, 125–129 (1982)MathSciNetMATH Peroche, B.: Complexité de l’arboricité linéaire d’un graphe. RAIRO Recherche Operationelle 16, 125–129 (1982)MathSciNetMATH
16.
Zurück zum Zitat Shermer, T.C.: On rectangle visibility graphs III: external visibility and complexity. In: Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG 1996), pp. 234–239 (1996) Shermer, T.C.: On rectangle visibility graphs III: external visibility and complexity. In: Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG 1996), pp. 234–239 (1996)
Metadaten
Titel
Trees, Paths, Stars, Caterpillars and Spiders
verfasst von
Minghui Jiang
Copyright-Jahr
2015
DOI
https://doi.org/10.1007/978-3-319-26626-8_40