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

被引：1
作者：
de Werra, D. [1 ]
Hammer, P. L.
机构：
[1] Ecole Polytech Fed Lausanne, IMA, CH-1015 Lausanne, Switzerland
[2] Rutgers State Univ, RUTCOR, Piscataway, NJ 08854 USA
来源：
ANNALS OF OPERATIONS RESEARCH | 2007年 / 149卷 / 01期
关键词：
Graph Transformation; Complete Bipartite Graph; Stability Number; Discrete Apply Mathematic; Complete Bipartite Subgraph;
D O I：
10.1007/s10479-006-0101-0
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
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. © 2006 Springer Science+Business Media, LLC.
引用
收藏
页码：67 / 73
页数：7
相关论文
共 9 条
[1]   Struction revisited [J].
Alexe, G ;
Hammer, PL ;
Lozin, VV ;
de Werra, D .
DISCRETE APPLIED MATHEMATICS, 2003, 132 (1-3) :27-46
[2]  
BERGE C, 1973, GRAPHS HYPERGAPHS
[3]  
Ebenegger Ch, 1984, N HOLLAND MATH STUDI, V95, P83, DOI [10.1016/S0304-0208(08)72955-4, DOI 10.1016/S0304-0208(08)72955-4]
[4]  
Garey MR, 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[5]   THE STRUCTION OF A GRAPH - APPLICATION TO CN-FREE GRAPHS [J].
HAMMER, PL ;
MAHADEV, NVR ;
DEWERRA, D .
COMBINATORICA, 1985, 5 (02) :141-147
[6]   STABILITY IN CAN-FREE GRAPHS [J].
HAMMER, PL ;
MAHADEV, NVR ;
DEWERRA, D .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 38 (01) :23-30
[7]  
HAMOR A, 1980, REGARDS THEORIE GRAP, P29
[8]   On the use of Boolean methods for the computation of the stability number [J].
Hertz, A .
DISCRETE APPLIED MATHEMATICS, 1997, 76 (1-3) :183-203
[9]   POLYNOMIALLY SOLVABLE CASES FOR THE MAXIMUM STABLE SET PROBLEM [J].
HERTZ, A .
DISCRETE APPLIED MATHEMATICS, 1995, 60 (1-3) :195-210
1