✦ LIBER ✦

Min–max tree covers of graphs

✍ Scribed by G. Even; N. Garg; J. Könemann; R. Ravi; A. Sinha

Publisher: Elsevier Science
Year: 2004
Tongue: English
Weight: 225 KB
Volume: 32
Category: Article
ISSN: 0167-6377
DOI: 10.1016/j.orl.2003.11.010

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Approximation hardness of min–max tree c

Approximation hardness of min–max tree covers

✍ Zhou Xu; Qi Wen 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 367 KB

We prove the first inapproximability bounds to study approximation hardness for a min-max k-tree cover problem and its variants. The problem is to find a set of k trees to cover vertices of a given graph with metric edge weights, so as to minimize the maximum total edge weight of any of the k trees.

Graph Searching and a Min-Max Theorem fo

Graph Searching and a Min-Max Theorem for Tree-Width

✍ P.D. Seymour; R. Thomas 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 474 KB

Min-max Computation Tree Logic

✍ Pallab Dasgupta; P.P. Chakrabarti; Jatindra Kumar Deka; Sriram Sankaranarayanan 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 342 KB

This paper introduces a branching time temporal query language called Min-max CTL which is similar in syntax to the popular temporal logic, CTL [Clarke et al., ACM Trans. Program. Lang. Systems 8 (1986) 244]. However unlike CTL, Min-max CTL can express timing queries on a timed model. We show that i

A min-max relation for K3-covers in grap

A min-max relation for K3-covers in graphs noncontractible to K5e

✍ Ali Ridha Mahjoub 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 628 KB

Not Every Uniform Tree Covers Ramanujan

Not Every Uniform Tree Covers Ramanujan Graphs

✍ Alexander Lubotzky; Tatiana Nagnibeda 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 297 KB

The notion of Ramanujan graph has been extended to not necessarily regular graphs by Y. Greenberg. We construct infinite trees with infinitely many finite quotients, none of which is Ramanujan. We give a sufficient condition for a finite graph to be covered by such a tree.

Approximation Algorithms for Min–Max Tre

Approximation Algorithms for Min–Max Tree Partition

✍ Nili Guttmann-Beck; Refael Hassin 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 298 KB

We consider the problem of partitioning the node set of a graph into p equal sized subsets. The objective is to minimize the maximum length, over these subsets, of a minimum spanning tree. We show that no polynomial algorithm with bounded Ž 2 . error ratio can be given for the problem unless P s NP.