Displaying similar documents to “The Uniform Minimum-Ones 2SAT Problem and its Application to Haplotype Classification”

Hypergraphs with large transversal number and with edge sizes at least four

Michael Henning, Christian Löwenstein (2012)

Open Mathematics

Similarity:

Let H be a hypergraph on n vertices and m edges with all edges of size at least four. The transversal number τ(H) of H is the minimum number of vertices that intersect every edge. Lai and Chang [An upper bound for the transversal numbers of 4-uniform hypergraphs, J. Combin. Theory Ser. B, 1990, 50(1), 129–133] proved that τ(H) ≤ 2(n+m)/9, while Chvátal and McDiarmid [Small transversals in hypergraphs, Combinatorica, 1992, 12(1), 19–26] proved that τ(H) ≤ (n + 2m)/6. In this paper, we...

Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP

Edith Hemaspaandra, Jörg Rothe, Holger Spakowski (2006)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

For both the edge deletion heuristic and the maximum-degree greedy heuristic, we study the problem of recognizing those graphs for which that heuristic can approximate the size of a minimum vertex cover within a constant factor of r , where r is a fixed rational number. Our main results are that these problems are complete for the class of problems solvable via parallel access to NP . To achieve these main results, we also show that the restriction of the vertex cover problem to those graphs...

The Capacitated Arc Routing Problem. A heuristic algorithm.

Enrique. Benavent, V. Campos, Angel Corberán, Enrique Mota (1990)

Qüestiió

Similarity:

In this paper we consider the Capacitated Arc Routing Problem, in which a fleet of K vehicles, all of them based on a specific vertex (the depot) and with a known capacity Q, must service a subset of the edges of the graph, with minimum total cost and such that the load assigned to each vehicle does not exceed its capacity. A heuristic algorithm for this problem is proposed consisting of: the selection of K centers, the construction of K connected graphs with associated loads...