Name
Title | ||
|---|---|---|
Approximation Algorithms for Finding a Maximum-Weight Spanning Connected Subgraph with given Vertex Degrees |
Abstract | ||
|---|---|---|
In the paper a problem of finding a maximum-weight spanning connected subgraph with given vertex degrees is considered. The problem is MAX SNP-hard, because it is a generalization of a well-known Traveling Salesman Problem. Approximation algorithms are constructed for deterministic and random instances. Performance bounds of these algorithms are presented. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/3-540-27679-3_43 | Operations Research Proceedings |
Field | DocType | ISSN |
Approximation algorithm,Discrete mathematics,Mathematical optimization,Combinatorics,Vertex (geometry),Performance ratio,Travelling salesman problem,Vertex connectivity,Mathematics | Conference | 0721-5924 |
Citations | PageRank | References |
4 | 0.91 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexey Baburin | 1 | 9 | 2.23 |
| Edward Gimadi | 2 | 12 | 5.32 |