About: The k-dimensional Weisfeiler-Leman procedure ([Formula: see text]) has proven to be immensely fruitful in the algorithmic study of Graph Isomorphism. More generally, it is of fundamental importance in understanding and exploiting symmetries in graphs in various settings. Two graphs are [Formula: see text]-equivalent if dimention k does not suffice to distinguish them. [Formula: see text]-equivalence is known as fractional isomorphism of graphs, and the [Formula: see text]-equivalence relation becomes finer as k increases. We investigate to what extent standard graph parameters are preserved by [Formula: see text]-equivalence, focusing on fractional graph packing numbers. The integral packing numbers are typically NP-hard to compute, and we discuss applicability of [Formula: see text]-invariance for estimating the integrality gap of the LP relaxation provided by their fractional counterparts.   Goto Sponge  NotDistinct  Permalink

An Entity of Type : fabio:Abstract, within Data Space : covidontheweb.inria.fr associated with source document(s)

AttributesValues
type
value
  • The k-dimensional Weisfeiler-Leman procedure ([Formula: see text]) has proven to be immensely fruitful in the algorithmic study of Graph Isomorphism. More generally, it is of fundamental importance in understanding and exploiting symmetries in graphs in various settings. Two graphs are [Formula: see text]-equivalent if dimention k does not suffice to distinguish them. [Formula: see text]-equivalence is known as fractional isomorphism of graphs, and the [Formula: see text]-equivalence relation becomes finer as k increases. We investigate to what extent standard graph parameters are preserved by [Formula: see text]-equivalence, focusing on fractional graph packing numbers. The integral packing numbers are typically NP-hard to compute, and we discuss applicability of [Formula: see text]-invariance for estimating the integrality gap of the LP relaxation provided by their fractional counterparts.
Subject
  • Geometry
  • 20th-century American mathematicians
  • Morphisms
  • Equivalence (mathematics)
  • Missing person cases in Chile
part of
is abstract of
is hasSource of
Faceted Search & Find service v1.13.91 as of Mar 24 2020


Alternative Linked Data Documents: Sponger | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data]
OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software