A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs

DOI10.1016/j.tcs.2018.02.025zbMath1417.68147OpenAlexW2792054598WikidataQ57361238 ScholiaQ57361238MaRDI QIDQ1731506

Angelo Monti, Matteo Dell'Orefice, Tiziana Calamoneri

Publication date: 13 March 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/11573/1196846

zbMATH Keywords

planar graphschordal graphs2-treeslocally connected spanning treepartial \(k\) treesSC \(k\)-trees

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Unnamed Item
• Separating subgraphs in k-trees: Cables and caterpillars
• Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• On spanning 2-trees in a graph
• The complexity of the locally connected spanning tree problem
• Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs
• Parameterized complexity of the spanning tree congestion problem
• On simple characterizations of k-trees
• A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs
• Subclasses of \(k\)-trees: characterization and recognition
• Algorithmic Aspects of Vertex Elimination on Graphs
• Perfect k‐line graphs and k‐total graphs