On finding optimal and near-optimal lineal spanning trees
From MaRDI portal
Publication:1105381
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)
NP-completenessapproximation algorithmsconstraint satisfactiondepth-first searchlineal spanning trees
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