Back to Search
Start Over
A new algorithm for the maximum weighted stable set problem in claw-free graphs
- Source :
- IPCO 2008: Integer Programming and Combinatorial Optimization, IPCO 2008: Integer Programming and Combinatorial Optimization, May 2008, Bertinoro, Italy. pp.77-96, ⟨10.1007/978-3-540-68891-4_6⟩, Integer Programming and Combinatorial Optimization ISBN: 9783540688860, IPCO
- Publication Year :
- 2008
- Publisher :
- HAL CCSD, 2008.
-
Abstract
- In this paper, we introduce two powerful graph reductions for the maximum weighted stable set (mwss) in general graphs. We show that these reductions allow to reduce the mwss in claw-free graphs to the mwss in a class of quasi-line graphs, that we call bipolar-free. For this latter class, we provide a new algorithmic decomposition theorem running in polynomial time. We then exploit this decomposition result and our reduction tools again to transform the problem to either a single matching problem or a longest path computation in an acyclic auxiliary graph (in this latter part we use some results of Pulleyblank and Shepherd [10]). Putting all the pieces together, the main contribution of this paper is a new polynomial time algorithm for the mwss in claw-free graphs. A rough analysis of the complexity of this algorithm gives a time bound of O(n6), where n is the number of vertices in the graph, and which we hope can be improved by a finer analysis. Incidentally, we prove that the mwss problem can be solved efficiently for any class of graphs that admits a "suitable" decomposition into pieces where the mwss is easy.
- Subjects :
- Combinatorial optimization
Computer science
0211 other engineering and technologies
02 engineering and technology
Polynomials
01 natural sciences
Domain decomposition methods
Scheduling algorithms
Matching problems
Chordal graph
Polynomial-time algorithms
Longest path
ComputingMilieux_MISCELLANEOUS
decomposition theorems
021103 operations research
Quasi-line graphs
Mathematical programming
Integer programming
Longest path problem
Graph
Modular decomposition
010201 computation theory & mathematics
(algorithmic) complexity
Auxiliary graphs
Claw-free graphs
Mathematical transformations
Set theory
Settore MAT/09 - Ricerca Operativa
Algorithm
Algorithms
Optimization
Paper
Aerospace applications
Boolean functions
Combinatorial mathematics
Curve fitting
Dynamic programming
Evolutionary algorithms
Farm buildings
Graph theory
Linear programming
Nonlinear programming
Polynomial approximation
Reduction
Trees (mathematics)
General (CO)
graph reductions
international conferences
New algorithm
Polynomial-time
Reduction tools
Running in
time bound
0102 computer and information sciences
Combinatorics
Indifference graph
Pathwidth
Cograph
[INFO]Computer Science [cs]
Graph coloring
Time complexity
Discrete mathematics
1-planar graph
Vertex (geometry)
Independent set
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-540-68886-0
- ISBNs :
- 9783540688860
- Database :
- OpenAIRE
- Journal :
- IPCO 2008: Integer Programming and Combinatorial Optimization, IPCO 2008: Integer Programming and Combinatorial Optimization, May 2008, Bertinoro, Italy. pp.77-96, ⟨10.1007/978-3-540-68891-4_6⟩, Integer Programming and Combinatorial Optimization ISBN: 9783540688860, IPCO
- Accession number :
- edsair.doi.dedup.....527f3ec567e749f9eafaa3ad78aa62ea