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

graphs modelling interconnection networkspolynomial algorithm

Mathematics Subject Classification ID

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

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)

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

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)