Tight lower and upper bounds for the complexity of canonical colour refinement
From MaRDI portal
Publication:2398207
DOI10.1007/s00224-016-9686-0zbMath1368.68219arXiv1509.08251OpenAlexW2152691118WikidataQ59529126 ScholiaQ59529126MaRDI QIDQ2398207
Martin Grohe, Paul Bonsma, Christoph Berkholz
Publication date: 15 August 2017
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1509.08251
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
Isomorphism Testing for Graphs Excluding Small Minors, Quasifibrations of graphs to find symmetries and reconstruct biological networks, Unnamed Item, Lowerbounds for Bisimulation by Partition Refinement, From generic partition refinement to weighted tree automata minimization
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finite model theory and its applications.
- Elements of finite model theory.
- Circular Sturmian words and Hopcroft's algorithm
- A linear time solution to the single function coarsest partition problem
- Partitioning a graph in \(O(|A|\log_ 2|V|)\)
- An optimal lower bound on the number of variables for graph identification
- Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
- Practical graph isomorphism. II.
- Three Partition Refinement Algorithms
- Random Graph Isomorphism
- Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps
- Fibonacci heaps and their uses in improved network optimization algorithms
- Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs
- Implementation and Application of Automata
