On finding optimal and near-optimal lineal spanning trees
type: Item
instance of: scholarly article
title: On finding optimal and near-optimal lineal spanning trees
zbMATH Open document ID: 0648.68074
DOI: 10.1007/BF01762131
author: Michael R. Fellows
author: Donald K. Friesen
author: Michael A. Langston
published in: Algorithmica
publication date: 1988-01-01T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4058882
zbMATH Keywords: constraint satisfaction
zbMATH Keywords: depth-first search
zbMATH Keywords: NP-completeness
zbMATH Keywords: lineal spanning trees
zbMATH Keywords: approximation algorithms
Wikidata QID: Q57360176
MaRDI profile type: Publication
cites work: Q4198056
cites work: Efficient Planarity Testing
cites work: Q3862380
cites work: Q3924253
cites work: The logic of constraint satisfaction
cites work: Q4739657
cites work: Parallel Algorithms for Depth-First Searches I. Planar Graphs
cites work: Q3309631
cites work: An efficient parallel algorithm for shifting the root of a depth first spanning tree
cites work: Finding triconnected components of graphs
cites work: Q4552272
Recommended article: Near-optimal bounded-degree spanning trees
Recommended article: Approximating Maximum Leaf Spanning Trees in Almost Linear Time
Recommended article: On the approximability of some maximum spanning tree problems
Recommended article: On the approximability of some Maximum Spanning Tree Problems
Recommended article: A randomized linear-time algorithm for finding minimum spanning trees (extended abstract)
Recommended article: Near-linear time algorithm for approximate minimum degree spanning trees
Recommended article: Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
Recommended article: A randomized linear-time algorithm to find minimum spanning trees
Recommended article: Q2753956
description: scientific article; zbMATH DE number 4058882