✦ LIBER ✦

On Minimum Edge Ranking Spanning Trees

✍ Scribed by Kazuhisa Makino; Yushi Uno; Toshihide Ibaraki

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 243 KB
Volume: 38
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2000.1143

No coin nor oath required. For personal study only.

✦ Synopsis

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. Furthermore, we present an approximation algorithm for MERST, which realizes its worst case performance ratio min * -1 log n/ * * -1 log * + 1 -1 where n is the number of vertices in G and * is the maximum degree of a spanning tree whose maximum degree is minimum. Although the approximation algorithm is a combination of two existing algorithms for the restricted spanning tree problem and for the minimum edge ranking problem of trees, the analysis is based on novel properties of the edge ranking of trees.

📜 SIMILAR VOLUMES

A note on bisecting minimum spanning tre

A note on bisecting minimum spanning trees

✍ W. M. Boyce; M. R. Garey; D. S. Johnson 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 281 KB

Counting Minimum Weight Spanning Trees

✍ Andrei Z. Broder; Ernst W. Mayr 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 152 KB

We present an algorithm for counting the number of minimum weight spanning trees, based on the fact that the generating function for the number of spanning trees of a given graph, by weight, can be expressed as a simple determinant. For a graph with n vertices and m edges, our Ž Ž .. Ž . algorithm r

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

The Capacitated Minimum Spanning Tree

✍ K. M. Chandy; Tachen Lo 📂 Article 📅 1973 🏛 John Wiley and Sons 🌐 English ⚖ 386 KB

## Abstract The capacitated minimum spanning tree is an offspring of the minimum spanning tree and network flow problems. It has application in the design of multipoint linkages in elementary teleprocessing tree networks. Some theorems are used in conjunction with Little's branch and bound algorith

Average distance, minimum degree, and sp

Average distance, minimum degree, and spanning trees

✍ Dankelmann, Peter; Entringer, Roger 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 218 KB

The average distance µ(G) of a connected graph G of order n is the average of the distances between all pairs of vertices of G, i.e., µ(G) = ( n 2 ) -1 {x,y}⊂V (G) d G (x, y), where V (G) denotes the vertex set of G and d G (x, y) is the distance between x and y. We prove that every connected graph

Minimum Spanning Trees and Types of Diss

Minimum Spanning Trees and Types of Dissimilarities

✍ Bruno Leclerc 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 295 KB