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

DOI10.1016/j.ipl.2010.09.008zbMath1379.05111OpenAlexW2038917364MaRDI QIDQ1675823

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

algorithmsNP-completenessgraph algorithmslocally connected spanning tree

Mathematics Subject Classification ID

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

Related Items (2)

Computing a minimum outer-connected dominating set for the class of chordal graphs ⋮ A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs

Cites Work

• Unnamed Item
• Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
• Complement reducible graphs
• On spanning 2-trees in a graph
• The complexity of the locally connected spanning tree problem
• Incidence matrices and interval graphs
• Steiner trees, partial 2–trees, and minimum IFI networks
• A Linear Recognition Algorithm for Cographs
• Networks immune to isolated failures
• Dually Chordal Graphs

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