Name
Abstract | ||
|---|---|---|
We present a new "primal" algorithm for the stable set problem. It is based on a purely combinatorial construction that can transform every graph into a perfect graph by replacing nodes with sets of new nodes. The transformation is done in such a way that every stable set in the perfect graph corresponds to a stable set in the original graph. The algorithm keeps a formulation of the stable set problem in a simplex-type tableau whose associated basic feasible solution is the incidence vector of the best known stable set. The combinatorial graph transformations are performed by substitutions in the generators of the feasible region. Each substitution cuts off a fractional neighbor of the current basic feasible solution. We show that "dual-type" polynomial-time separation algorithms carry over to our "primal" setting. Eventually, either a nondegenerate pivot leading to an integral basic feasible solution is performed, or the optimality of the current solution is proved. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1007/3-540-45749-6_47 | ESA |
Keywords | Field | DocType |
associated basic feasible solution,stable set problem,original graph,combinatorial graph transformation,feasible region,current basic feasible solution,perfect graph corresponds,primal approach,current solution,stable set,perfect graph,polynomial time,graph transformation | Perfect graph,Strength of a graph,Discrete mathematics,Combinatorics,Computer science,Graph factorization,Directed graph,Independent set,Null graph,Feedback arc set,Complement graph | Conference |
Volume | ISSN | ISBN |
2461 | 0302-9743 | 3-540-44180-8 |
Citations | PageRank | References |
1 | 0.37 | 7 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| C. Gentile | 1 | 104 | 7.94 |
| Utz-Uwe Haus | 2 | 226 | 18.47 |
| Matthias KöPpe | 3 | 191 | 20.95 |
| Giovanni Rinaldi | 4 | 151 | 20.50 |
| Robert Weismantel | 5 | 964 | 90.05 |