\(k\)-connectivity and decomposition of graphs into forests

DOI10.1016/0166-218X(94)90015-9zbMath0818.05043MaRDI QIDQ1343147

Takao Nishizeki, Svatopluk Poljak

Publication date: 1 February 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

decompositionforests\(k\)-connectivityspanning trees

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Connectivity (05C40)

Related Items

Sparse connectivity certificates via MA orderings in graphs ⋮ \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms ⋮ A linear time algorithm for computing 3-edge-connected components in a multigraph ⋮ Sparse graph certificates for mixed connectivity ⋮ On sparse subgraphs preserving connectivity properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the thickness and arboricity of a graph
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Bounds of the number of disjoint spanning trees
• Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen