Name
Abstract | ||
|---|---|---|
The reoptimization issue studied in this paper can be described as follows: given an instance I of some problem Pi, an optimal solution OPT in I and an instance I' resulting from a local perturbation of I that consists of insertions or removals of a small number of data, we wish to use OPT to solve Pi in I', either optimally or by guaranteeing an approximation ratio better than that guaranteed by an ex nihilo computation and with running time better than that needed for such a computation. We use this setting to study weighted versions of MAX P-k-FREE Subgraph and MAX PLANAR SUBGRAPH, which are representatives of a broad class of problems known in the literature as maximum induced hereditary subgraph problems. We also show that the techniques presented allow us to handle BIN PACKING. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1142/S1793830913600045 | DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Vertex (geometry),Induced subgraph isomorphism problem,Planar,Subgraph isomorphism problem,Bin packing problem,Mathematics,Computation | Journal | 5 |
Issue | ISSN | Citations |
2 | 1793-8309 | 1 |
PageRank | References | Authors |
0.35 | 11 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicolas Boria | 1 | 59 | 7.23 |
| Jérôme Monnot | 2 | 512 | 55.74 |
| Vangelis Th. Paschos | 3 | 633 | 63.97 |