Finding, Minimizing, and Counting Weighted Subgraphs
From MaRDI portal
Publication:2848203
DOI10.1137/09076619XzbMath1275.68080OpenAlexW1996791172MaRDI QIDQ2848203
Virginia Vassilevska Williams, R. Ryan Williams
Publication date: 25 September 2013
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/09076619x
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (25)
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Quantum algorithm for triangle finding in sparse graphs ⋮ Quasipolynomiality of the Smallest Missing Induced Subgraph ⋮ Quantum algorithms for finding constant-sized sub-hypergraphs ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts ⋮ Universal Hashing via Integer Arithmetic Without Primes, Revisited ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ Unnamed Item ⋮ Sublinear-time algorithms for counting star subgraphs via edge sampling ⋮ Quantum algorithm design: techniques and applications ⋮ Algebraic methods in the congested clique ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sequential Monte Carlo for maximum weight subgraphs with application to solving image jigsaw puzzles ⋮ Unnamed Item ⋮ Hamming Distance Completeness ⋮ Counting Answers to Existential Questions ⋮ Approximate Counting of k-Paths: Deterministic and in Polynomial Space ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ The fine-grained complexity of multi-dimensional ordering properties ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time ⋮ Unnamed Item
This page was built for publication: Finding, Minimizing, and Counting Weighted Subgraphs
