• français
    • English
  • français 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Reoptimization of maximum weight induced hereditary subgraph problems

Thumbnail
View/Open
cahier_311.pdf (557.4Kb)
Date
2013
Dewey
Recherche opérationnelle
Sujet
reoptimization
Journal issue
Theoretical Computer Science
Volume
514
Publication date
2013
Article pages
61-74
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.tcs.2012.10.037
URI
https://basepub.dauphine.fr/handle/123456789/7388
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Boria, Nicolas
Paschos, Vangelis
Monnot, Jérôme
Type
Article accepté pour publication ou publié
Abstract (EN)
The reoptimization issue studied in this paper can be described as follows: given aninstance I of some problem Π, an optimal solution O P T for Π in I and an instance I ′ resultingfrom a local perturbation of I that consists of insertions or removals of a small number ofdata, we wish to use O P T in order to solve Π in I ′, either optimally or by guaranteeingan approximation ratio better than that guaranteed by an ex nihilo computation and withrunning time better that that needed for such a computation. We use this setting in order tostudy weighted versions of several representatives of a broad class of problems known in theliterature as maximum induced hereditary subgraph problems. The main problems studiedare max independent set, max k -colorable subgraph, max Pk-free subgraph, maxsplit subgraph and max planar subgraph. We also show, how the techniques presentedallow us to handle also bin packing.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.