Decomposable trees: A polynomial algorithm for tripodes

DOI10.1016/S0166-218X(00)00322-XzbMATH Open1002.68107OpenAlexW2053543588MaRDI QIDQ1613342FDOQ1613342

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (32)

• 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
• 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
• An Ore-type condition for arbitrarily vertex decomposable graphs
• A degree bound on decomposable trees
• 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
• Closure results for arbitrarily partitionable graphs
• Title not available (Why is that?)
• Dense arbitrarily partitionable graphs
• Arbitrarily edge-partitionable graphs
• Arbitrarily vertex decomposable suns with few rays
• On-line arbitrarily vertex decomposable suns
• 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
• Some properties of minimal arbitrarily partitionable graphs
• An Ore-type condition for arbitrarily vertex decomposable graphs
• Fully decomposable split graphs
• 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)