✦ LIBER ✦

An Efficient Polynomial Time Approximation Scheme for the Constrained Minimum Spanning Tree Problem Using Matroid Intersection

✍ Scribed by Hassin, Refael; Levin, Asaf

Book ID: 118180435
Publisher: Society for Industrial and Applied Mathematics
Year: 2004
Tongue: English
Weight: 143 KB
Volume: 33
Category: Article
ISSN: 0097-5397
DOI: 10.1137/s0097539703426775

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A fully polynomial bicriteria approximat

A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem

✍ Sung-Pil Hong; Sung-Jin Chung; Bum Hwan Park 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 213 KB

We propose a fully polynomial bicriteria approximation scheme for the constrained spanning tree problem. First, an exact pseudo-polynomial algorithm is developed based on a two-variable extension of the well-known matrix-tree theorem. The scaling and approximate binary search techniques are then uti

A Polynomial Time Approximation Scheme f

A Polynomial Time Approximation Scheme for the Grade of Service Steiner Minimum Tree Problem

✍ Joonmo Kim; Mihaela Cardei; Ionut Cardei; Xiaohua Jia 📂 Article 📅 2002 🏛 Springer US 🌐 English ⚖ 230 KB

An Unconditional Lower Bound on the Time

An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem

✍ Elkin, Michael 📂 Article 📅 2006 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 330 KB