On spanning 2-trees in a graph

DOI10.1016/S0166-218X(96)00045-5zbMath0883.05040MaRDI QIDQ1356500

Leizhen Cai

Publication date: 16 March 1998

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

approximation algorithmspanning trees

Mathematics Subject Classification ID

Trees (05C05)

Related Items

Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs, Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs, On a characterization of k-trees, Maximum series-parallel subgraph, The complexity of the locally connected spanning tree problem, A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs, Spanning trees: A survey, Plane Triangulations Without Spanning 2-Trees, A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs, Tree 3-spanners on interval, permutation and regular bipartite graphs, Exact solution to an extremal problem on graphic sequences with a realization containing every 2-tree on \(k\) vertices, Complexity of some graph-based bounds on the probability of a union of events, On the complexity of some subgraph problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the SPANNING \(k\)-TREE problem
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• A proof of the Gilbert-Pollak conjecture on the Steiner ratio
• Networks immune to isolated failures
• Tree Spanners