ISSN:
1432-0541
Keywords:
Spanning tree
;
Isomorphism
;
Tree spanner
;
Algorithm
;
NP-complete
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract A treet-spanner, wheret is a positive integer, of a graph G is a spanning tree in which the distance between the two ends of every edge ofG is at mostt. This notion is motivated by applications in distributed systems and communication networks. This paper is concerned with the problem of determining whether a graph contains a tree t-spanner isomorphic to a given tree. It is shown that the problem fort=2 is solvable in O(n3.5) time for 2-connected graphs, whereas the problem for any fixed integert ≥ 3 is NP-complete, even for 2-connected bipartite graphs.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01293665
Permalink
