Weighted stability number of graphs and weighted satisfiability: The two facets of pseudo-Boolean optimization

被引：0

作者：

D. de Werra

P. L. Hammer

机构：

[1] IMA - EPFL,

[2] RUTCOR,undefined

[3] Rutgers University,undefined

来源：

Annals of Operations Research | 2007年 / 149卷

关键词：

Graph Transformation; Complete Bipartite Graph; Stability Number; Discrete Apply Mathematic; Complete Bipartite Subgraph;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

We exhibit links between pseudo-Boolean optimization, graph theory and logic. We show the equivalence of maximizing a pseudo-Boolean function and finding a maximum weight stable set; symmetrically minimizing a pseudo-Boolean function is shown to be equivalent to solving a weighted satisfiability problem.

引用

页码：67 / 73

页数：6

共 14 条

[1]

Alexe A.(2004)Struction Revisited Discrete Applied Mathematics 132 27-46

[2]

Hammer P.L.(1984)Pseudoboolean Functions and Stability of Graphs Annals of Discrete Mathematics 19 83-98

[3]

Lozin V.V.(1995)Polynomially Solvable Cases for the Maximum Stable Set Problem Discrete Applied Mathematics 60 195-210

[4]

Werra D. de(1985)On the Use of Boolean Methods for the Computation of the Stability Number Discrete Applied Mathematics 76 183-203

[5]

Ebenegger C.(1985)Stability in CAN-Free Graphs J. Combin. Theory B38 23-30

[6]

Hammer P.L.(1985)The Struction of a Graph: Applications to CN-Free Graphs Combinatorica 5 141-147

[7]

Werra D. de(undefined)undefined undefined undefined undefined-undefined

[8]

Hertz A.(undefined)undefined undefined undefined undefined-undefined

[9]

Hertz A.(undefined)undefined undefined undefined undefined-undefined

[10]

Hammer P.L.(undefined)undefined undefined undefined undefined-undefined

← 1 2 →