Listing 4-cycles

DOI10.4230/LIPICS.FSTTCS.2023.25MaRDI QIDQ6951710zbMATH OpenFDO

Authors Amir Abboud, Seri Khoury, Oree Leibowitz, Ron Safier

Publication date 28 July 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2023.25

zbMATH Keywords

cycles listingfine-grained complexitygraph algorithmssubgraph detection

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites work

• A New Algorithm for Generating All the Maximal Independent Sets
• An Optimal Algorithm for Triangle Counting in the Stream
• Arboricity and Subgraph Listing Algorithms
• Detecting short directed cycles using rectangular matrix multiplication and dynamic programming
• Distributed triangle detection via expander decomposition
• Enumeration complexity of conjunctive queries with functional dependencies
• Finding All the Elementary Circuits of a Directed Graph
• Finding and counting given length cycles
• Finding and counting small induced subgraphs efficiently
• Finding Even Cycles Even Faster
• Finding even cycles faster via capped k-walks
• Finding four-node subgraphs in triangle time
• First-order queries on structures of bounded degree are computable with constant delay
• Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond
• Higher lower bounds from the 3SUM conjecture
• scientific article; zbMATH DE number 3910446 (Why is no real title available?)
• scientific article; zbMATH DE number 3937199 (Why is no real title available?)
• scientific article; zbMATH DE number 7788370 (Why is no real title available?)
• Improved quantum algorithm for triangle finding via combinatorial arguments
• Listing triangles
• Monochromatic triangles, triangle listing and APSP
• On Acyclic Conjunctive Queries and Constant Delay Enumeration
• On the complexity of fixed parameter clique and dominating set
• Optimal listing of cycles and st-paths in undirected graphs
• Quantum Algorithms for the Triangle Problem
• Removing additive structure in 3SUM-based reductions
• Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
• Supersaturation of even linear cycles in linear hypergraphs
• The number of \(C_{2\ell}\)-free graphs
• Towards polynomial lower bounds for dynamic problems

This page was built for publication: Listing 4-cycles

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