Find link

language:

Find link is a tool written by Edward Betts.

Longer titles found: Vertex cover in hypergraphs (view)

searching for Vertex cover 17 found (95 total)

Domination analysis (512 words) [view diff] case mismatch in snippet view article find links to article

Inapproximability. Let ε > 0. Unless P=NP, there is no polynomial algorithm for Vertex Cover such that its domination number is greater than 3^((n-n^ε)/3). Inapproximability

Truncated projective plane (1,223 words) [view diff] no match in snippet view article find links to article

The minimum fractional vertex-cover size of the TPP is r-1 too: assigning a weight of 1/r to each vertex (which is a vertex-cover since each hyperedge contains

Irit Dinur (374 words) [view diff] case mismatch in snippet view article find links to article

her thesis was entitled On the Hardness of Approximating the Minimum Vertex Cover and The Closest Vector in a Lattice. She joined the Weizmann Institute

K-approximation of k-hitting set (778 words) [view diff] case mismatch in snippet view article find links to article

Bar-Yehuda (1981). "A Linear-Time Approximation Algorithm for the Weighted Vertex Cover Problem". J. Algorithms. 2 (2): 198–203. doi:10.1016/0196-6774(81)90020-1

Matroid rank (1,429 words) [view diff] exact match in snippet view article find links to article

Don; Vishkin, Uzi (1985), "Solving NP-hard problems in 'almost trees': Vertex cover", Discrete Applied Mathematics, 10 (1): 27–45, doi:10.1016/0166-218X(85)90057-5

Dilworth's theorem (2,369 words) [view diff] exact match in snippet view article find links to article

chains in P form a matching in the graph. The complement of A forms a vertex cover in G with the same cardinality as this matching. This connection to bipartite

European Symposium on Algorithms (604 words) [view diff] case mismatch in snippet view article find links to article

lattice 2016 Stefan Kratsch: A randomized polynomial kernelization for Vertex Cover with a smaller parameter Thomas Bläsius, Tobias Friedrich, Anton Krohmer

Robertson–Seymour theorem (2,515 words) [view diff] exact match in snippet view article find links to article

For instance, by this result, treewidth, branchwidth, and pathwidth, vertex cover, and the minimum genus of an embedding are all amenable to this approach

Circuit rank (1,612 words) [view diff] exact match in snippet view article find links to article

Don; Vishkin, Uzi (1985), "Solving NP-hard problems in 'almost trees': Vertex cover", Discrete Applied Mathematics, 10 (1): 27–45, doi:10.1016/0166-218X(85)90057-5

Disjunctive Datalog (344 words) [view diff] exact match in snippet view article find links to article

salesman problem, graph coloring, maximum clique problem, and minimal vertex cover. These problems are only expressible in Datalog if the polynomial hierarchy

Eternal dominating set (1,786 words) [view diff] exact match in snippet view article find links to article

on the eternal domination problem were proposed including the eternal vertex cover problem, the eternal independent set problem, eternal total dominating

Maximum coverage problem (1,761 words) [view diff] case mismatch in snippet view article find links to article

S. (1997). "Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and Related Problems". In Hochbaum, Dorit S. (ed.)

Contraction hierarchies (3,381 words) [view diff] case mismatch in snippet view article find links to article

Siddharth; Zych-Pawlewicz, Anna (2022). "On Sparse Hitting Sets: From Fair Vertex Cover to Highway Dimension". In Dell, Holger; Nederlof, Jesper (eds.). 17th

Clique problem (9,876 words) [view diff] case mismatch in snippet view article find links to article

Valiente, Gabriel (2002), "Chapter 6: Clique, Independent Set, and Vertex Cover", Algorithms on Trees and Graphs, Springer, pp. 299–350, doi:10

Ahlswede–Khachatrian theorem (1,988 words) [view diff] exact match in snippet view article find links to article

Irit; Safra, Shmuel (2005). "On the hardness of approximating minimum vertex cover". Annals of Mathematics. 162 (1): 439–485. doi:10.4007/annals.2005.162

Highway dimension (2,656 words) [view diff] case mismatch in snippet view article find links to article

Siddharth; Zych-Pawlewicz, Anna (2022). "On Sparse Hitting Sets: From Fair Vertex Cover to Highway Dimension". Proceedings of 17th International Symposium on

Parameterized approximation algorithm (3,277 words) [view diff] case mismatch in snippet view article find links to article

ε>0{\displaystyle \varepsilon >0}. For example, while the Connected Vertex Cover problem is FPT parameterized by the solution size, it does not admit