Exploiting a Hypergraph Model for Finding Golomb Rulers

DOI10.1007/978-3-642-32147-4_33zbMath1360.68519OpenAlexW1862050608MaRDI QIDQ3167640

Mathias Weller, Hannes Moser, Manuel Sorge, Rolf Niedermeier

Publication date: 2 November 2012

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-32147-4_33

zbMATH Keywords

data reductionNP-hardnessparameterized complexityhitting setproblem kernelforbidden subgraph characterization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Exploiting a hypergraph model for finding Golomb rulers ⋮ Towards optimal and expressive kernelization for \(d\)-hitting set