Martin Milanič (Avtor), Jérôme Monnot (Avtor)

Povzetek

The exact weighted independent set (EWIS) problem consists in determining whether a given vertex-weighted graph contains an independent set of given weight. This problem is a generalization of two well-known problems, the NP-complete subset sum problem and the strongly NP-hard maximum weight independent set (MWIS) problem. Since the MWIS problem is polynomially solvable for some special graph classes, it is interesting to determine the complexity of this more general EWIS problem for such graph classes. We focus on the class of perfect graphs, which is one of the most general graph classes where the MWIS problem can be solved in polynomial time. It turns out that for certain subclasses of perfect graphs, the EWIS problem is solvable in pseudopolynomial time, while on some others it remains strongly NP-complete.In particular, we show that the EWIS problem is strongly NP-complete for bipartite graphs of maximum degree three, but solvable in pseudo-polynomial time for cographs, interval graphs and chordal graphs, as well as for some other related graph classes.

Ključne besede

graf;neodvisna množica;popolni graf;dvodelni graf;graph theory;complexity;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.08 - Objavljeni znanstveni prispevek na konferenci
Organizacija: UP - Univerza na Primorskem
UDK: 519.17
COBISS: 1024190548 Povezava se bo odprla v novem oknu
ISSN: 1571-0653
Matična publikacija: ǂThe ǂV Latin-American Algorithms, Graphs, and Optimization Symposium
Št. ogledov: 2694
Št. prenosov: 116
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Neznan jezik
Sekundarne ključne besede: graph theory;complexity;
Vrsta dela (COBISS): Delo ni kategorizirano
Strani: Str. 317-322
Zvezek: ǂVol. ǂ35
Čas izdaje: 2009
DOI: 10.1016/j.endm.2009.11.052
ID: 1493176
Priporočena dela:
, ni podatka o podnaslovu
, Workshop on information theory and related fields, Bielefeld, December 03 - 06, 2007
, ni podatka o podnaslovu