Partitioning a graph in \(O(|A|\log_ 2|V|)\)

DOI10.1016/0304-3975(82)90016-0zbMath0478.68067OpenAlexW2002279082WikidataQ61677993 ScholiaQ61677993MaRDI QIDQ1161293

S. Singh

Publication date: 1982

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(82)90016-0

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Quasifibrations of graphs to find symmetries and reconstruct biological networks, FACTOR MAPS OF LAMBDA-GRAPH SYSTEMS AND INCLUSIONS OF C*-ALGEBRAS, Tight lower and upper bounds for the complexity of canonical colour refinement, An algorithmic view of gene teams, Graph isomorphism, color refinement, and compactness, On the Power of Color Refinement, Lowerbounds for Bisimulation by Partition Refinement, Calcul de la distance par les sous-mots, An optimal algorithm for computing the repetitions in a word, A logical framework for privacy-preserving social network publication, Minimisation of acyclic deterministic automata in linear time, Fast algorithms for identifying maximal common connected sets of interval graphs, Set constraints and logic programming, Re-describing an algorithm by Hopcroft, Graph fibrations, graph isomorphism, and PageRank

Cites Work

• On the computational power of pushdown automata
• The graph isomorphism disease
• An Efficient Algorithm for Graph Isomorphism
• Unnamed Item
• Unnamed Item