ZIB

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

On the spanning trees of weighted graphs (1992)

Mayr, Ernst W. ; Plaxton, C. Greg

Springer

Combinatorica 12 (1992), S. 433-447

add to mindlist on the mindlist

Details

ISSN: 1439-6912

Keywords: 05 C 05 ; 05 C 85 ; 68 R 10

Source: Springer Online Journal Archives 1860-2000

Topics: Mathematics

Notes: Abstract Given a weighted graph, letW 1,W 2,W 3,... denote the increasing sequence of all possible distinct spanning tree weights. Settling a conjecture due to Kano, we prove that every spanning tree of weightW 1 is at mostk−1 edge swaps away from some spanning tree of weightW k . Three other conjectures posed by Kano are proven for two special classes of graphs. Finally, we consider the algorithmic complexity of generating a spanning tree of weightW k .

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF01305236

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit