On the Weisfeiler-Leman dimension of fractional packing

DOI10.1007/978-3-030-40608-0_25zbMath1437.68134arXiv1910.11325OpenAlexW3013401877MaRDI QIDQ5896136

Oleg Verbitsky, Frank Fuhlbrück, V. Arvind, Johannes Köbler

Publication date: 27 July 2020

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityfractional packingWeisfeiler-Leman algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Fractional graph theory, fuzzy graph theory (05C72) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (3)

On the Weisfeiler-Leman dimension of fractional packing ⋮ The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw ⋮ Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm

This page was built for publication: On the Weisfeiler-Leman dimension of fractional packing