Finding and counting cliques and independent sets in \(r\)-uniform hypergraphs
From MaRDI portal
Publication:845699
DOI10.1016/J.IPL.2006.04.005zbMath1184.05088OpenAlexW2011367822WikidataQ56210450 ScholiaQ56210450MaRDI QIDQ845699
Publication date: 29 January 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2006.04.005
Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (5)
Positive independence densities of finite rank countable hypergraphs are achieved by finite hypergraphs ⋮ The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics ⋮ On vertex independence number of uniform hypergraphs ⋮ Hypergraph Independent Sets ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
Cites Work
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- On the complexity of fixed parameter clique and dominating set
- Matrix multiplication via arithmetic progressions
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- On Sets of Acquaintances and Strangers at any Party
- Large Cliques Elude the Metropolis Process
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Finding and counting cliques and independent sets in \(r\)-uniform hypergraphs
