Decomposing trees with large diameter

DOI10.1016/j.tcs.2010.04.032zbMath1209.05052OpenAlexW1966882057MaRDI QIDQ986542

Romain Ravaux

Publication date: 11 August 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.04.032

zbMATH Keywords

diameterinteger partitionarbitrarily partitionable trees

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph designs and isomorphic decomposition (05C51)

Related Items

Dense on-line arbitrarily partitionable graphs ⋮ Partitioning powers of traceable or Hamiltonian graphs ⋮ Unnamed Item ⋮ On minimal arbitrarily partitionable graphs ⋮ Partitioning the Cartesian product of a tree and a cycle ⋮ Arbitrarily partitionable \(\{2K_2, C_4\}\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• A linear-time algorithm for four-partitioning four-connected planar graphs
• A linear algorithm for bipartition of biconnected graphs
• On the shape of decomposable trees
• Decomposable trees: A polynomial algorithm for tripodes
• A degree bound on decomposable trees
• On arbitrarily vertex decomposable trees
• A homology theory for spanning tress of a graph