Lupa

Show document Help

A- | A+ | Print
Title:The exact weighted independent set problem in perfect graphs and related classes
Authors:ID Milanič, Martin (Author)
ID Monnot, Jérôme (Author)
Files:URL http://dx.doi.org/10.1016/j.endm.2009.11.052
 
Language:English
Work type:Not categorized
Typology:1.08 - Published Scientific Conference Contribution
Organization:IAM - Andrej Marušič Institute
Abstract: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.
Keywords:graf, neodvisna množica, popolni graf, dvodelni graf
Year of publishing:2009
Number of pages:Str. 317-322
Numbering:Vol. 35
PID:20.500.12556/RUP-2747 This link opens in a new window
ISSN:1571-0653
UDC:519.17
COBISS.SI-ID:1024190548 This link opens in a new window
Publication date in RUP:15.10.2013
Views:2769
Downloads:116
Metadata:XML RDF-CHPDL DC-XML DC-RDF
:
Copy citation
  
Average score:(0 votes)
Your score:Voting is allowed only for logged in users.
Share:Bookmark and Share


Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Secondary language

Language:Unknown
Keywords:graph theory, complexity


Comments

Leave comment

You must log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica