Name
Title | ||
|---|---|---|
A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem |
Abstract | ||
|---|---|---|
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 utilized to yield a fully polynomial approximation scheme. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.orl.2003.06.003 | Oper. Res. Lett. |
Keywords | Field | DocType |
bicriteria approximation,tree problem,polynomial bicriteria approximation scheme,fully polynomial approximation scheme,polynomial approximation scheme,approximate binary search technique,well-known matrix-tree theorem,two-variable extension,matrix-tree theorem,spanning tree,exact pseudo-polynomial algorithm,binary search | Discrete mathematics,Mathematical optimization,Combinatorics,Polynomial,k-minimum spanning tree,Polynomial remainder theorem,Connected dominating set,Spanning tree,Matrix polynomial,Mathematics,Polynomial-time approximation scheme,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
32 | 3 | Operations Research Letters |
Citations | PageRank | References |
26 | 1.41 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sung-Pil Hong | 1 | 137 | 13.07 |
| Sung-Jin Chung | 2 | 72 | 8.21 |
| Bum Hwan Park | 3 | 45 | 3.09 |