Top

Published in:

2015 | OriginalPaper | Chapter

Trees, Paths, Stars, Caterpillars and Spiders

Author : Minghui Jiang

Published in: Combinatorial Optimization and Applications

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

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.

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 Dynamic Single-Source Shortest Paths in Erdös-Rényi Random Graphs

next chapter Algorithms for the Densest Subgraph with at Least k Vertices and with a Specified Subset

Akiyama, J., Exoo, G., Harary, F.: Covering and packing in graphs III: cyclic and acyclic invariants. Math. Slovoca 30, 405–417 (1980)MathSciNetMATH

Alon, N.: The linear arboricity of graphs. Israel J. Math. 62, 311–325 (1988)MathSciNetCrossRefMATH

Cygan, M., Hou, J., Kowalik, Ł., Lužar, B., Wu, J.: A planar linear arboricity conjecture. J. Graph Theor. 69, 403–425 (2012)MathSciNetCrossRefMATH

Fiala, J., Jansen, K., Le, V.B., Seidel, E.: Graph subcolorings: complexity and algorithms. SIAM J. Discrete Math. 16, 635–650 (2003)MathSciNetCrossRefMATH

Gabow, H.N., Westermann, H.H.: Forests, frames, and games: algorithms for matroid sums and applications. Algorithmica 7, 465–497 (1992)MathSciNetCrossRefMATH

Gimbel, J., Hartman, C.: Subcolorings and the subchromatic number of a graph. Discrete Math. 272, 139–154 (2003)MathSciNetCrossRefMATH

Gonçalves, D.: Caterpillar arboricity of planar graphs. Discrete Math. 307, 2112–2121 (2007)MathSciNetCrossRefMATH

Gonçalves, D., Ochem, P.: On star and caterpillar arboricity. Discrete Math. 309, 3694–3702 (2009)MathSciNetCrossRefMATH

Hakimi, S.L., Mitchem, J., Schmeichel, E.: Star arboricity of graphs. Discrete Math. 149, 93–98 (1996)MathSciNetCrossRefMATH

10.

Jiang, M.: Recognizing \(d\)-interval graphs and \(d\)-track interval graphs. Algorithmica 66, 541–563 (2013)MathSciNetCrossRefMATH

11.

Klein, P., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. Algorithms 19, 104–115 (1995)MathSciNetCrossRefMATH

12.

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.

Maffray, F., Preissmann, M.: On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs. Discrete Math. 162, 313–317 (1996)MathSciNetCrossRefMATH

14.

Nash-Williams, C.S.J.A.: Decomposition of finite graphs into forests. J. Lond. Math. Soc. 39, 12 (1964)MathSciNetCrossRefMATH

15.

Peroche, B.: Complexité de l’arboricité linéaire d’un graphe. RAIRO Recherche Operationelle 16, 125–129 (1982)MathSciNetMATH

16.

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)

Title: Trees, Paths, Stars, Caterpillars and Spiders
Author: Minghui Jiang
Publisher: Springer International Publishing
Book: Combinatorial Optimization and Applications
Print ISBN: 978-3-319-26625-1

Electronic ISBN: 978-3-319-26626-8

Copyright Year: 2015
DOI: https://doi.org/10.1007/978-3-319-26626-8_40

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner