Dimension Reduction via Colour Refinement

DOI10.1007/978-3-662-44777-2_42zbMath1425.68313arXiv1307.5697OpenAlexW2963879148MaRDI QIDQ2921438

Erkal Selman, Kristian Kersting, Martin Mladenov, Martin Grohe

Publication date: 8 October 2014

Published in: Algorithms - ESA 2014 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1307.5697

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) 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 (9)

Characterizing and computing weight-equitable partitions of graphs ⋮ Graph isomorphism, color refinement, and compactness ⋮ On the Power of Color Refinement ⋮ Dimension reduction for semidefinite programs via Jordan algebras ⋮ Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic ⋮ Relational linear programming ⋮ On the Weisfeiler-Leman dimension of fractional packing ⋮ Unnamed Item ⋮ On the expressive power of linear algebra on graphs

This page was built for publication: Dimension Reduction via Colour Refinement