Finding, minimizing, and counting weighted subgraphs

DOI10.1145/1536414.1536477zbMath1304.05102OpenAlexW2080525033WikidataQ56210447 ScholiaQ56210447MaRDI QIDQ5172740

R. Ryan Williams, Virginia Vassilevska Williams

Publication date: 4 February 2015

Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1536414.1536477

zbMATH Keywords

pathsweighted graphcliquessubgraph isomorphism3SUM

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Signed and weighted graphs (05C22)

Related Items (21)

Knapsack problem with objective value gaps ⋮ Counting Subgraphs in Degenerate Graphs ⋮ The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics ⋮ Simple paths with exact and forbidden lengths ⋮ Exact Weight Subgraphs and the k-Sum Conjecture ⋮ Counting Homomorphic Cycles in Degenerate Graphs ⋮ Evaluation of permanents in rings and semirings ⋮ Faster algorithms for finding and counting subgraphs ⋮ Are unique subgraphs not easier to find? ⋮ Cliques enumeration and tree-like resolution proofs ⋮ Fast monotone summation over disjoint sets ⋮ Detecting and Counting Small Pattern Graphs ⋮ Diversity metrics for direct-coded variable-length chromosome shortest path problem evolutionary algorithms ⋮ Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more ⋮ Extreme witnesses and their applications ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ Balanced Hashing, Color Coding and Approximate Counting ⋮ On Multidimensional and Monotone k-SUM ⋮ Unique subgraphs are not easier to find ⋮ Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles ⋮ 3SUM, 3XOR, triangles

This page was built for publication: Finding, minimizing, and counting weighted subgraphs