𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A polynomial algorithm for minimal interval representation

✍ Scribed by Anat Fischer; Itzhak Gilboa; Moshe Shpitalni

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
929 KB
Volume
13
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Polynomial time algorithms for computing
Polynomial time algorithms for computing a representation for minimal unsatisfiable formulas with fixed deficiency
✍ Hans Kleine BΓΌning; Xishun Zhao πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 72 KB

We say a propositional formula F in conjunctive normal form is represented by a formula H and a homomorphism Ο†, if Ο†(H ) = F . A homomorphism is a mapping consisting of a renaming and an identification of literals. The deficiency of a formula is the difference between the number of clauses and the n

A Combinatorial Algorithm Minimizing Sub
A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time
✍ Alexander Schrijver πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 108 KB

We give a strongly polynomial-time algorithm minimizing a submodular function f given by a value-giving oracle. The algorithm does not use the ellipsoid method or any other linear programming method. No bound on the complexity of the values of f is needed to be known a priori. The number of oracle c

A zero-free interval for chromatic polyn
A zero-free interval for chromatic polynomials
✍ D.R. Woodall πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 458 KB

Woodall, D.R., A zero-free interval for chromatic polynomials, Discrete Mathematics 101 (1992) 333-341. It is proved that, for a wide class of near-triangulations of the plane, the chromatic polynomial has no zeros between 2 and 2.5. Together with a previously known result, this shows that the zero