Finding and counting given length cycles
From MaRDI portal
Publication:675293
DOI10.1007/BF02523189zbMath0865.68093OpenAlexW1967066104MaRDI QIDQ675293
Uri Zwick, Raphael Yuster, Noga Alon
Publication date: 6 March 1997
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02523189
Related Items
Subquadratic-time algorithm for the diameter and all eccentricities on median graphs ⋮ On linear algebraic algorithms for the subgraph matching problem and its variants ⋮ Topological network entanglement as order parameter for the emergence of geometry ⋮ Finding small complete subgraphs efficiently ⋮ On claw-free asteroidal triple-free graphs ⋮ Parameterized graph separation problems ⋮ Parameterized coloring problems on chordal graphs ⋮ On triangle estimation using tripartite independent set queries ⋮ On the Combinatorial Power of the Weisfeiler-Lehman Algorithm ⋮ The many facets of the Estrada indices of graphs and networks ⋮ Counting Subgraphs in Degenerate Graphs ⋮ Finding and counting small induced subgraphs efficiently ⋮ Fast Output-Sensitive Matrix Multiplication ⋮ A Task-Scheduling Approach for Efficient Sparse Symmetric Matrix-Vector Multiplication on a GPU ⋮ Stability structures of conjunctive Boolean networks ⋮ The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics ⋮ The complexity of multiple handed self-assembly ⋮ Testing for Equivalence of Network Distribution Using Subgraph Counts ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Triangle counting in dynamic graph streams ⋮ A nice class for the vertex packing problem ⋮ On cube-free median graphs ⋮ Equimatchable claw-free graphs ⋮ Treewidth for graphs with small chordality ⋮ Answering conjunctive queries with inequalities ⋮ Recognizing graphs without asteroidal triples ⋮ Complex networks: structure and dynamics ⋮ Finding a sun in building-free graphs ⋮ Quantum algorithm for triangle finding in sparse graphs ⋮ A general purpose algorithm for counting simple cycles and simple paths of any length ⋮ Counting Homomorphic Cycles in Degenerate Graphs ⋮ On the negative cost girth problem in planar networks ⋮ Find subtrees of specified weight and cycles of specified length in linear time ⋮ Triangle‐free equimatchable graphs ⋮ Number of cycles of small length in a graph ⋮ Approximately Counting Triangles in Sublinear Time ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ Colorful triangle counting and a \textsc{MapReduce} implementation ⋮ Arboricity, \(h\)-index, and dynamic algorithms ⋮ Lazy or eager dynamic matching may not be fast ⋮ Lengths of words accepted by nondeterministic finite automata ⋮ Bounds and algorithms for graph trusses ⋮ Are unique subgraphs not easier to find? ⋮ Extended dynamic subgraph statistics using \(h\)-index parameterized data structures ⋮ A Hopf algebra for counting cycles ⋮ Sublinear-time algorithms for counting star subgraphs via edge sampling ⋮ Unnamed Item ⋮ Computing the rooted triplet distance between galled trees by counting triangles ⋮ FURL: fixed-memory and uncertainty reducing local triangle counting for multigraph streams ⋮ Method for quickly inferring the mechanisms of large-scale complex networks based on the census of subgraph concentrations ⋮ Two-walks degree assortativity in graphs and networks ⋮ Efficient and Adaptive Parameterized Algorithms on Modular Decompositions ⋮ Finding and counting given length cycles ⋮ Parity check matrices and product representations of squares ⋮ Maximum cardinality neighbourly sets in quadrilateral free graphs ⋮ Detecting induced subgraphs ⋮ Main-memory triangle computations for very large (sparse (power-law)) graphs ⋮ Enumerating simple paths from connected induced subgraphs ⋮ An Efficient Algorithm for Helly Property Recognition in a Linear Hypergraph ⋮ Complexity issues for the sandwich homogeneous set problem ⋮ Algebraic methods in the congested clique ⋮ On the complexity of fixed parameter clique and dominating set ⋮ Unnamed Item ⋮ Efficient algorithms for clique problems ⋮ Efficient approximation algorithms for shortest cycles in undirected graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the characteristic polynomial of the power of a path. ⋮ On the expressive power of linear algebra on graphs ⋮ Counting Subgraphs in Relational Event Graphs ⋮ Sparse matrix multiplication and triangle listing in the congested clique model ⋮ Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs ⋮ Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP ⋮ Unnamed Item ⋮ Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments ⋮ Integral regular net-balanced signed graphs with vertex degree at most four ⋮ Detecting directed 4-cycles still faster ⋮ Counting Triangles under Updates in Worst-Case Optimal Time ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ Clique Counting in MapReduce ⋮ Why Do Simple Algorithms for Triangle Enumeration Work in the Real World? ⋮ Triangle edge deletion on planar glasses-free RGB-digraphs ⋮ A parameterized view on matroid optimization problems ⋮ Improved distance queries and cycle counting by Frobenius normal form ⋮ On Generating Triangle-Free Graphs ⋮ Evaluating Datalog via tree automata and cycluits ⋮ Balanced Hashing, Color Coding and Approximate Counting ⋮ Linear time algorithms for finding a dominating set of fixed size in degenerated graphs ⋮ Immersed cycles and the JSJ decomposition ⋮ Unnamed Item ⋮ Local Graph Stability in Exponential Family Random Graph Models ⋮ Time Windowed Data Structures for Graphs ⋮ Unique subgraphs are not easier to find ⋮ Graph Classes and Forbidden Patterns on Three Vertices ⋮ The fine-grained complexity of multi-dimensional ordering properties ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Unnamed Item ⋮ Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles ⋮ Unnamed Item ⋮ 3SUM, 3XOR, triangles
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding and counting small induced subgraphs efficiently
- Finding and counting given length cycles
- Cycles of even length in graphs
- Arboricity and Subgraph Listing Algorithms
- Finding short cycles in planar graphs using separators
- Smallest-last ordering and clustering and graph coloring algorithms
- Finding a Minimum Circuit in a Graph
- Finding Even Cycles Even Faster
- Color-coding
- Recognizing small subgraphs
- On generalized graphs
