• 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

The complexity of the exact weighted independent set problem

Monnot, Jérôme; Milanic, Martin (2008), The complexity of the exact weighted independent set problem, in Paschos, Vangelis, Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives: : 30th anniversary of the LAMSADE, Wiley : Hoboken (NJ), p. 393-432. http://dx.doi.org/10.1002/9780470611098.ch16

View/Open
Wiley-ISTE_ExactWIS.pdf (340.3Kb)
Type
Chapitre d'ouvrage
Date
2008
Book title
Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives: : 30th anniversary of the LAMSADE
Book author
Paschos, Vangelis
Publisher
Wiley
Published in
Hoboken (NJ)
ISBN
978-1-8482-1021-9
Number of pages
515
Pages
393-432
Publication identifier
http://dx.doi.org/10.1002/9780470611098.ch16
Metadata
Show full item record
Author(s)
Monnot, Jérôme cc
Milanic, Martin
Abstract (EN)
In this paper, we introduce the exact weighted independent set problem (EWIS), the problem of determining whether a given weighted graph contains an independent set of a given weight. Our motivation comes from the related exact perfect matching problem, whose computational complexity is still unknown. We determine the complexities of the EWIS problem and its restricted version EWIS (where the independent set is required to be of maximum size) for several graph classes. These problems are strongly NP-complete for cubic bipartite graphs; we also extend this result to a more general setting. On the positive side, we show that EWIS and EWIS can be solved in pseudo-polynomial time for chordal graphs, AT-free graphs, distance-hereditary graphs, circle graphs, graphs of bounded clique-width, and several subclasses of P5-free and fork-free graphs. In particular, we show how modular decomposition can be applied to the exact weighted independent set problem.
Subjects / Keywords
bipartite graph; optimization problems; pseudo-polynomial time; practical importance; polynomial results

Related items

Showing items related by title and author.

  • Thumbnail
    On the complexity of the exact weighted independent set problem 
    Milanic, Martin; Monnot, Jérôme (2007) Document de travail / Working paper
  • Thumbnail
    The exact weighted independent set problem in perfect graphs and related classes 
    Monnot, Jérôme; Milanic, Martin (2009) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and algorithms for constant diameter augmentation problems 
    Kim, Eun Jung; Milanic, Martin; Monnot, Jérôme; Picouleau, Christophe (2022) Article accepté pour publication ou publié
  • Thumbnail
    On the maximum independent set problem in subclasses of subcubic graphs 
    Ries, Bernard; Monnot, Jérôme; Lozin, Vadim (2015) Article accepté pour publication ou publié
  • Thumbnail
    On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs 
    Lozin, Vadim; Monnot, Jérôme; Ries, Bernard (2013) 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