Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs

DOI10.1016/J.IPL.2010.09.008MaRDI QIDQ1675823zbMATH OpenOpenAlexFDO

Authors Peng Zhang

Publication date 3 November 2017

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2010.09.008

zbMATH Keywords

algorithmsgraph algorithmslocally connected spanning treeNP-completeness

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
• The complexity of the locally connected spanning tree problem
• scientific article; zbMATH DE number 1979496
• A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs
• A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs

Cites work

• A Linear Recognition Algorithm for Cographs
• Complement reducible graphs
• Dually Chordal Graphs
• scientific article; zbMATH DE number 1234609 (Why is no real title available?)
• Incidence matrices and interval graphs
• Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
• Networks immune to isolated failures
• On spanning 2-trees in a graph
• Steiner trees, partial 2–trees, and minimum IFI networks
• The complexity of the locally connected spanning tree problem

Cited in

(5)

• The complexity of the locally connected spanning tree problem
• A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs
• A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs
• Computing a minimum outer-connected dominating set for the class of chordal graphs
• Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

This page was built for publication: Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs

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