𝔖 Bobbio Scriptorium
✦   LIBER   ✦

MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability

✍ Scribed by Zhao Xing; Weixiong Zhang

Publisher
Elsevier Science
Year
2005
Tongue
English
Weight
327 KB
Volume
164
Category
Article
ISSN
0004-3702

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

An Efficient Algorithm for Minimum-Weigh
An Efficient Algorithm for Minimum-Weight Bibranching
✍ J. Keijsper; R. Pendavingh πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 280 KB

Given a directed graph D=(V, A) and a set S V, a bibranching is a set of arcs B A that contains a v&(V "S) path for every v # S and an S&v path for every v # V "S. In this paper, we describe a primal dual algorithm that determines a minimum weight bibranching in a weighted digraph. It has running ti

An Efficient Exact Algorithm for Constra
An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover
✍ Henning Fernau; Rolf Niedermeier πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 382 KB

The constraint bipartite vertex cover problem (CBVC for short) is as follows: given a bipartite graph G with n vertices and two positive integers k 1 k 2 , is there a vertex cover taking at most k 1 vertices from one and at most k 2 vertices from the other vertex set of G? CBVC is NP-complete. It fo

Efficient algorithms for finding maximum
Efficient algorithms for finding maximum cliques of an overlap graph
✍ Sumio Masuda; Kazuo Nakajima; Toshinobu Kashiwabara; Toshio Fujisawa πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 728 KB

Let F = { I , , 12,. . . , Z,,} be a finite family of closed intervals on the real line. Two intervals 4 and Ik in F are said to overlap each other if they intersect but neither one of them contains the other. A graph G = (V, E) is called an overlap graph for F if there is a one-to-one correspondenc