Complexité de l'arboricité linéaire d'un graphe

DOI10.1051/ro/1982160201251zbMath0492.05025OpenAlexW2488617184MaRDI QIDQ3953783

Bernard Peroche

Publication date: 1982

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/104805

zbMATH Keywords

linear arboricitychains forestsN.P.-complexity

Mathematics Subject Classification ID

Trees (05C05) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (13)

A Planar linear arboricity conjecture ⋮ Recognizing \(d\)-interval graphs and \(d\)-track interval graphs ⋮ Trees, paths, stars, caterpillars and spiders ⋮ Trees, Paths, Stars, Caterpillars and Spiders ⋮ An efficient case for computing minimum linear arboricity with small maximum degree ⋮ Minimum number of disjoint linear forests covering a planar graph ⋮ On an \(f\)-coloring generalization of linear arboricity of multigraphs ⋮ On the complexity of deciding whether the regular number is at most two ⋮ The linear arboricity of planar graphs with no short cycles ⋮ Linear arboricity of outer-1-planar graphs ⋮ On linear k-arboricity ⋮ Linear \(k\)-arboricities on trees ⋮ The linear arboricity of \(K_5\)-minor free graphs

This page was built for publication: Complexité de l'arboricité linéaire d'un graphe