Name
Title | ||
|---|---|---|
Weighted stability number of graphs and weighted satisfiability: The two facets of pseudo-Boolean optimization |
Abstract | ||
|---|---|---|
We exhibit links between pseudo-Boolean optimization, graph theory and logic. We show the equivalence of maximizing a pseudo-Boolean func- tion and finding a maximum weight stable set; symmetrically minimizing a pseudo-Boolean function is shown to be equivalent to solving a weighted satisfiability problem. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/s10479-006-0101-0 | Annals OR |
Keywords | Field | DocType |
Graph Transformation,Complete Bipartite Graph,Stability Number,Discrete Apply Mathematic,Complete Bipartite Subgraph | Maximum satisfiability problem,Graph theory,Complete bipartite graph,Discrete mathematics,Combinatorics,Mathematical optimization,Satisfiability,Boolean satisfiability problem,Equivalence (measure theory),Independent set,And-inverter graph,Mathematics | Journal |
Volume | Issue | ISSN |
149 | 1 | 0254-5330 |
Citations | PageRank | References |
1 | 0.36 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dominique de Werra | 1 | 495 | 84.31 |
| Peter L. Hammer | 2 | 1996 | 288.93 |