Name
Abstract | ||
|---|---|---|
Let T be a given tree. Each vertex of T is either a supply vertex or a demand vertex, and is assigned a positive integer, called the supply or the demand. Every
demand vertex v of T must be supplied an amount of “power,” equal to the demand of v, from exactly one supply vertex through edges in T. Each edge e of T has a direction, and is assigned a positive integer which represents the cost required to delete e from T or reverse the direction of e. Then one wishes to obtain subtrees of T by deleting edges and reversing the directions of edges so that (a) each subtree contains exactly one supply vertex whose
supply is no less than the sum of all demands in the subtree and (b) each subtree is rooted at the supply vertex in a sense
that every edge is directed away from the root. We wish to minimize the total cost to obtain such rooted subtrees from T. In the paper, we first show that this minimization problem is NP-hard, and then give a pseudo-polynomial-time algorithm
to solve the problem. We finally give a fully polynomial-time approximation scheme (FPTAS) for the problem.
|
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-17514-5_30 | Algorithmica |
Keywords | DocType | Volume |
Approximation algorithm,Demand vertex,Directed edge,FPTAS,Graph partition,Supply vertex,Tree | Journal | 64 |
Issue | ISSN | Citations |
3 | 0178-4617 | 5 |
PageRank | References | Authors |
0.43 | 5 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takehiro Ito | 1 | 260 | 40.71 |
| Takuya Hara | 2 | 5 | 0.43 |
| Xiao Zhou | 3 | 325 | 43.69 |
| Takao Nishizeki | 4 | 1771 | 267.08 |