On finding optimal and near-optimal lineal spanning trees

DOI10.1007/BF01762131zbMath0648.68074WikidataQ57360176 ScholiaQ57360176MaRDI QIDQ1105381

Michael A. Langston, Donald K. Friesen, Michael R. Fellows

Publication date: 1988

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

NP-completenessapproximation algorithmsconstraint satisfactiondepth-first searchlineal spanning trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (6)

On the approximability of some maximum spanning tree problems ⋮ On the approximability of some Maximum Spanning Tree Problems ⋮ On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves ⋮ Recognition of DFS trees: Sequential and parallel algorithms with refined verifications ⋮ Complexity of independency and cliquy trees ⋮ Resource allocation under limited sharing

Cites Work

• The logic of constraint satisfaction
• Finding triconnected components of graphs
• An efficient parallel algorithm for shifting the root of a depth first spanning tree
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• Efficient Planarity Testing
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On finding optimal and near-optimal lineal spanning trees