• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

Reoptimization under Vertex Insertion: Max Pk-Free Subgraph and Max Planar Subgraph

Boria, Nicolas; Monnot, Jérôme; Paschos, Vangelis (2013), Reoptimization under Vertex Insertion: Max Pk-Free Subgraph and Max Planar Subgraph, Discrete Mathematics, Algorithms and Applications, 05, 02, p. n°1360004. 10.1142/S1793830913600045

Type
Article accepté pour publication ou publié
Date
2013
Journal name
Discrete Mathematics, Algorithms and Applications
Volume
05
Number
02
Pages
n°1360004
Publication identifier
10.1142/S1793830913600045
Metadata
Show full item record
Author(s)
Boria, Nicolas cc
Monnot, Jérôme cc
Paschos, Vangelis
Abstract (EN)
The reoptimization issue studied in this paper can be described as follows: given an instance I of some problem Π, 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 Π 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 Pk-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.
Subjects / Keywords
reoptimization

Related items

Showing items related by title and author.

  • Thumbnail
    Reoptimization of the Maximum Weighted Pk-Free Subgraph Problem under Vertex Insertion 
    Boria, Nicolas; Monnot, Jérôme; Paschos, Vangelis (2012) Communication / Conférence
  • Thumbnail
    Reoptimization of maximum weight induced hereditary subgraph problems 
    Boria, Nicolas; Paschos, Vangelis; Monnot, Jérôme (2013) Article accepté pour publication ou publié
  • Thumbnail
    On the MAX MIN VERTEX COVER problem 
    Boria, Nicolas; Della Croce, Federico; Paschos, Vangelis (2014) Communication / Conférence
  • Thumbnail
    Local approximation for maximum H0-free partial subgraph problems 
    Monnot, Jérôme; Paschos, Vangelis; Toulouse, S. (2003) Article accepté pour publication ou publié
  • Thumbnail
    The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet 
    Boria, Nicolas; Gourvès, Laurent; Paschos, Vangelis; Monnot, Jérôme (2021) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo