Applications of matroid partition to tree decomposition

DOI10.1007/BF02677680MaRDI QIDQ1568255zbMATH OpenOpenAlexFDO

Authors Mao-Cheng Cai, Xudong Yuan

Publication date 29 November 2000

Published in Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02677680

zbMATH Keywords

decompositionmatroidpartitiontree

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

Edmonds' matroid partition theorem is applied to obtain alternative proofs of two tree decomposition theorems due to Shi Minyong. As an application, a necessary and sufficient condition for a connected graph to have a tree decomposition into two trees of order \(n-1\) is derived.

Recommendations

• A decomposition theory for matroids. I: General results
• On decomposing a hypergraph into \(k\) connected sub-hypergraphs
• A decomposition theory for matroids. IV: Decomposition of graphs
• Tree decomposition

Cites work

• A note on the tree decompositions of graphs
• Edge-Disjoint Spanning Trees of Finite Graphs
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• Minimum partition of a matroid into independent subsets
• On the Problem of Decomposing a Graph into n Connected Factors
• Some Abstract Pivot Algorithms
• Tree decomposition
• Two trees in maximal planar bipartite graphs

Cited in

(3)

• A unified treatment of linked and lean tree-decompositions
• Branch decomposition heuristics for linear matroids
• scientific article; zbMATH DE number 952954 (Why is no real title available?)

This page was built for publication: Applications of matroid partition to tree decomposition

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