The exponential time hypothesis and the parameterized clique problem
From MaRDI portal
Publication:4899237
DOI10.1007/978-3-642-33293-7_4zbMATH Open1374.68239OpenAlexW35149855MaRDI QIDQ4899237FDOQ4899237
Authors: Yijia Chen, Kord Eickmeyer, Jörg Flum 
Publication date: 7 January 2013
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-33293-7_4
Recommendations
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Sparsification and subexponential approximation
- On parameterized exponential time complexity
- On hardness of approximating the parameterized clique problem
- Linear FPT reductions and computational lower bounds
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (8)
- Maximum bipartite subgraphs of geometric intersection graphs
- Boolean functional synthesis: hardness and practical algorithms
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- An exact exponential time algorithm for counting bipartite cliques
- Lower bounds based on the exponential time hypothesis
- Tractable representations for Boolean functional synthesis
- Exact exponential-time algorithms for finding bicliques
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
This page was built for publication: The exponential time hypothesis and the parameterized clique problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4899237)
