Name
Abstract | ||
|---|---|---|
We present a new approach for approximating node deletion problems by combining the local ratio and the greedy multicovering algorithms. For a function f:V(G) → N, our approach allows to design a 2 + maxv∈V(G)logf(v) approximation algorithm for the problem of deleting a minimum number of nodes so that the degree of each node v in the remaining graph is at most f(v). This approximation ratio is shown to be asymptotically optimal. The new method is also used to design a 1 + (log 2)(k - 1) approximation algorithm for the problem of deleting a minimum number of nodes so that the remaining graph contains no k-bicliques. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/j.ipl.2003.08.005 | Inf. Process. Lett. |
Keywords | Field | DocType |
approximation ratio,node deletion problem,local ratio,new method,minimum number,approximation algorithm,remaining graph,new approach,node v,greedy multicovering algorithm,approximation algorithms | Graph theory,Approximation algorithm,Discrete mathematics,Graph,Combinatorics,Node deletion,Numerical approximation,Numerical analysis,Asymptotically optimal algorithm,Mathematics,Graph Node | Journal |
Volume | Issue | ISSN |
88 | 5 | 0020-0190 |
Citations | PageRank | References |
8 | 0.50 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Okun | 1 | 40 | 3.33 |
| Amnon Barak | 2 | 590 | 119.00 |