Fully dynamic four-vertex subgraph counting

DOI10.4230/LIPICS.SAND.2022.18MaRDI QIDQ7395555zbMATH OpenFDO

Authors Kathrin Hanauer, Monika R. Henzinger, Qi Cheng Hua

Publication date 2022

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.SAND.2022.18

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A dynamic data structure for counting subgraphs in sparse graphs
• A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
• Counting triangles in massive graphs with MapReduce
• Counting Triangles under Updates in Worst-Case Optimal Time
• Extended dynamic subgraph statistics using h-index parameterized data structures
• Finding and counting given length cycles
• Finding and counting small induced subgraphs efficiently
• scientific article; zbMATH DE number 3790470 (Why is no real title available?)
• scientific article; zbMATH DE number 2119719 (Why is no real title available?)
• scientific article; zbMATH DE number 7788448 (Why is no real title available?)
• If the current clique algorithms are optimal, so is Valiant's parser
• Powers of tensors and fast matrix multiplication
• The h-Index of a Graph and its Application to Dynamic Subgraph Statistics
• Tight hardness for shortest cycles and paths in sparse graphs
• Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture

This page was built for publication: Fully dynamic four-vertex subgraph counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7395555)