✦ LIBER ✦

A note on bisecting minimum spanning trees

✍ Scribed by W. M. Boyce; M. R. Garey; D. S. Johnson

Publisher: John Wiley and Sons
Year: 1978
Tongue: English
Weight: 281 KB
Volume: 8
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.3230080302

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On Minimum Edge Ranking Spanning Trees

✍ Kazuhisa Makino; Yushi Uno; Toshihide Ibaraki 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 243 KB

In this paper, we introduce the problem of computing a minimum edge ranking spanning tree (MERST); i.e., find a spanning tree of a given graph G whose edge ranking is minimum. Although the minimum edge ranking of a given tree can be computed in polynomial time, we show that problem MERST is NP-hard.

A note on graphs with diameter-preservin

A note on graphs with diameter-preserving spanning trees

✍ Fred Buckley; Martin Lewinter 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 182 KB 👁 1 views

The distance between a pair of vertices u, u in a graph G is the length of a shortest path joining u and u. The diameter diam(G) of G is the maximum distance between all pairs of vertices in G. A spanning tree Tof G is diameter preserving if diam(T) = diam(G). In this note, we characterize graphs th

On finding a minimum spanning tree in a

On finding a minimum spanning tree in a network with random weights

✍ Colin McDiarmid; Theodore Johnson; Harold S. Stone 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 221 KB 👁 2 views

We investigate Prim's standard ''tree-growing'' method for finding a minimum spanning tree, when applied to a network in which all degrees are about d and the edges e Ž . have independent identically distributed random weights w e . We find that when the kth ' Ž . edge e is added to the current tree

A Property on Edge-disjoint Spanning Tre

A Property on Edge-disjoint Spanning Trees

✍ Hong-Jian Lai; Hongyuan Lai; Charles Payan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 214 KB

Let G be a simple graph with n vertices and let G c denote the complement of G . Let ( G ) denote the number of components of G and G ( E ) the spanning subgraph of G with edge set E . where the minimum is taken over all such partitions . In [ Europ . J . Combin . 7 (1986) , 263 -270] , Payan conj

A note on genetic algorithms for degree-

A note on genetic algorithms for degree-constrained spanning tree problems

✍ Zhou, Gengui; Gen, Mitsuo 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 58 KB 👁 2 views

The degree-constrained spanning tree problem is of high practical importance. Up to now, there are few effective algorithms to solve this problem because of its NP-hard complexity. In this paper, we present a new approach to solve this problem by using genetic algorithms and computational results to

A 2-path approach for odd-diameter-const

A 2-path approach for odd-diameter-constrained minimum spanning and Steiner trees

✍ Luis Gouveia; Thomas L. Magnanti; Cristina Requejo 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB