Finding Four-Node Subgraphs in Triangle Time

DOI10.1137/1.9781611973730.111zbMath1371.05292OpenAlexW4247746673MaRDI QIDQ5363056

Huacheng Yu, Joshua R. Wang, Virginia Vassilevska Williams, R. Ryan Williams

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973730.111

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Finding Induced Subgraphs in Scale-Free Inhomogeneous Random Graphs ⋮ Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness] ⋮ The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems ⋮ Applying clique-decomposition for computing Gromov hyperbolicity ⋮ Induced subgraph isomorphism: are some patterns substantially easier than others? ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ Monotone arithmetic complexity of graph homomorphism polynomials ⋮ Linear‐time algorithms for eliminating claws in graphs ⋮ Parameterised and fine-grained subgraph counting, modulo 2 ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs ⋮ Are unique subgraphs not easier to find? ⋮ Revisiting Decomposition by Clique Separators ⋮ Unnamed Item ⋮ Counting Solutions to Polynomial Systems via Reductions ⋮ A Fast Deterministic Detection of Small Pattern Graphs in Graphs Without Large Cliques ⋮ A fast deterministic detection of small pattern graphs in graphs without large cliques ⋮ Unnamed Item ⋮ Detecting and Counting Small Pattern Graphs ⋮ Intersection graphs of non-crossing paths ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ When can graph hyperbolicity be computed in linear time? ⋮ Detecting and enumerating small induced subgraphs in \(c\)-closed graphs ⋮ Declawing a graph: polyhedra and branch-and-cut algorithms ⋮ Rare siblings speed-up deterministic detection and counting of small pattern graphs ⋮ Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles

This page was built for publication: Finding Four-Node Subgraphs in Triangle Time