About: On the Weisfeiler-Leman Dimension of Fractional Packing

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: On the Weisfeiler-Leman Dimension of Fractional Packing Goto Sponge NotDistinct Permalink

An Entity of Type : schema:ScholarlyArticle, within Data Space : wasabi.inria.fr associated with source document(s)

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
has title	On the Weisfeiler-Leman Dimension of Fractional Packing
Creator	Arvind, Vikraman Fuhlbrück, Frank Köbler, Johannes Verbitsky, Oleg
Source	PMC
abstract	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.
has issue date	2020-01-07(xsd:dateTime)
bibo:doi	10.1007/978-3-030-40608-0_25
has license	no-cc
sha1sum (hex)	1ff841fdd7a53860af654b9eed5812b2fb917ef4
schema:url	https://doi.org/10.1007/978-3-030-40608-0_25
resource representing a document's title	On the Weisfeiler-Leman Dimension of Fractional Packing
has PubMed Central identifier	PMC7206629
schema:publication	Language and Automata Theory and Applications
resource representing a document's body	covid:1ff841fdd7a53860af654b9eed5812b2fb917ef4#body_text
is schema:about of	named entity 'exploiting' named entity 'study' named entity 'STUDY' named entity 'SETTINGS' named entity 'GRAPH' named entity 'SYMMETRIES' covid:arg/1ff841fdd7a53860af654b9eed5812b2fb917ef4 named entity 'fixed-point logic' named entity 'vertex' named entity 'domination number' named entity 'graph' named entity 'k-dimensional' named entity 'adjacency matrix' named entity 'logic' named entity 'integer linear programs' named entity 'isomorphic' named entity 'vertex' named entity 'fundamental' named entity 'isomorphism' named entity 'graph' named entity 'graph' named entity 'graph' named entity 'vertices' named entity 'graph' named entity 'graph' named entity 'Dawar' named entity 'polynomial-time computable' named entity 'NP-hard' named entity 'lower bound' named entity 'homomorphic images' named entity 'isomorphic' named entity 'Hitting Set' named entity '1-dimensional' named entity 'general theorem' named entity 'probability' named entity 'matching number' named entity 'vertex' named entity 'indicator function' named entity 'probability 1' named entity 'Weisfeiler' named entity 'objective function' named entity 'linear program' named entity 'graphs' named entity 'Weisfeiler' named entity 'Weisfeiler' named entity 'cycle graph' named entity 'Lemma' named entity 'vertices' named entity 'graph' named entity 'vertex' named entity 'graph' named entity 'linear program' named entity 'graph' named entity 'vertices' named entity 'incidence graph' named entity 'linear programs' named entity 'integrality gap' named entity 'Disjoint' named entity 'vertices' named entity 'vertex' named entity 'Interpretability' named entity 'square matrix' named entity 'disjoint' named entity 'vertices' named entity 'doubly stochastic matrix' named entity 'integral graph' named entity 'algorithm' named entity 'vertex' named entity 'subgraph' named entity 'isomorphism' named entity 'isomorphic' named entity 'graph' named entity 'vertex' named entity 'Hitting Set' named entity 'doubly stochastic matrix' named entity '2-dimensional' named entity 'incidence matrices' named entity 'domination number' named entity 'domination number' named entity 'vertices'

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

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-2024 OpenLink Software