| Autor: |
Fellows, Michael, Friesen, Donald, Langston, Michael |
| Zdroj: |
Algorithmica; Nov1988, Vol. 3 Issue 1-4, p549-560, 12p |
| Abstrakt: |
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 finding optimal 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 unless P = NP. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
Full text from SpringerLink