On finding optimal and near-optimal lineal spanning trees |
| |
Authors: | Michael R Fellows Donald K Friesen and Michael A Langston |
| |
Affiliation: | (1) Department of Computer Science, University of Idaho, 83843 Moscow, ID, USA;(2) Department of Computer Science, Texas A&M University, 77840 College Station, TX, USA;(3) Department of Computer Science, Washington State University, 99164-1210 Pullman, WA, USA |
| |
Abstract: | The search for good lineal, or depth-first, spanning trees is an important aspect in the implementation of a wide assortment of graph algorithms. We consider the complexity of findingoptimal lineal spanning trees under various notions of optimality. In particular, we show that several natural problems, such as constructing a shortest or a tallest lineal tree, are NP-hard. We also address the issue of polynomial-time, near-optimization strategies for these difficult problems, showing that efficient absolute approximation algorithms cannot exist unlessP = NP.This author's research was supported in part by the Sandia University Research Program and by the National Science Foundation under Grant M IP-8603879.This author's research was supported in part by the National Science Foundation under Grants ECS-8403859 and MIP-8603879. |
| |
Keywords: | Lineal spanning trees Constraint satisfaction problems Depth-first search NP-completeness Approximation algorithms |
本文献已被 SpringerLink 等数据库收录! |
|