Finding large set covers faster via the representation method

DOI10.4230/LIPICS.ESA.2016.69MaRDI QIDQ4606341zbMATH OpenFDO

Authors Jesper Nederlof

Publication date 2 March 2018

Full work available at URL https://arxiv.org/abs/1608.03439

zbMATH Keywords

exact exponential algorithmsfine-grained complexityset cover

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Combinatorial optimization (90C27) Dynamic programming (90C39)

Recommendations

• Covering and Packing in Linear Space
• Covering and packing in linear space
• Set partitioning via inclusion-exclusion
• Exponential-time approximation of weighted set cover
• Approximating k-set cover and complementary graph coloring

Cited in

(5)

• The set cover conjecture and subgraph isomorphism with a tree pattern
• Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
• A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
• Fundamental problems on bounded-treewidth graphs: the real source of hardness
• Graph coloring below guarantees via co-triangle packing

This page was built for publication: Finding large set covers faster via the representation method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606341)