Decomposable trees: A polynomial algorithm for tripodes

DOI10.1016/S0166-218X(00)00322-XMaRDI QIDQ1613342zbMATH OpenOpenAlexFDO

Authors R. Smith

Publication date 29 August 2002

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

Full work available at URL https://doi.org/10.1016/s0166-218x(00)00322-x

zbMATH Keywords

polynomial algorithmgraphs modelling interconnection networks

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• A degree bound on decomposable trees
• On the shape of decomposable trees
• Fully decomposable split graphs
• Decomposing trees with large diameter
• Fully decomposable split graphs

Cited in

(35)

• Partitioning powers of traceable or Hamiltonian graphs
• Some families of arbitrarily vertex decomposable graphs
• Partitioning the Cartesian product of a tree and a cycle
• Decomposing trees with large diameter
• Interplays between variations of arbitrarily partitionable graphs under minimality constraints
• A _3 condition for arbitrarily partitionable graphs
• Arbitrarily partitionable \(\{2K_2, C_4\}\)-free graphs
• A polynomial algorithm for deciding the validity of an electrical distribution tree
• Dense on-line arbitrarily partitionable graphs
• On three polynomial kernels of sequences for arbitrarily partitionable graphs
• Fully decomposable split graphs
• Dense arbitrarily vertex decomposable graphs
• Cyclic sums, network sharing, and restricted edge cuts in graphs with long cycles
• A degree bound on decomposable trees
• An Ore-type condition for arbitrarily vertex decomposable graphs
• On arbitrarily vertex decomposable trees
• Partitioning the Cartesian product of a sun-like graph and a path
• More aspects of arbitrarily partitionable graphs
• On minimal arbitrarily partitionable graphs
• On the shape of decomposable trees
• scientific article; zbMATH DE number 4160782 (Why is no real title available?)
• Closure results for arbitrarily partitionable graphs
• Dense arbitrarily partitionable graphs
• Arbitrarily vertex decomposable suns with few rays
• On-line arbitrarily vertex decomposable suns
• Arbitrarily edge-partitionable graphs
• On the complexity of partitioning a graph into a few connected subgraphs
• Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
• Structural properties of recursively partitionable graphs with connectivity 2
• Toughness properties of arbitrarily partitionable graphs
• Some properties of minimal arbitrarily partitionable graphs
• An Ore-type condition for arbitrarily vertex decomposable graphs
• Partitioning vertices and edges of graphs into connected subgraphs
• On-line arbitrarily vertex decomposable trees
• Fully decomposable split graphs

This page was built for publication: Decomposable trees: A polynomial algorithm for tripodes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1613342)