On the Weisfeiler-Leman dimension of fractional packing
From MaRDI portal
Publication:5918531
DOI10.1016/j.ic.2021.104803OpenAlexW3215764949MaRDI QIDQ5918531
Oleg Verbitsky, Frank Fuhlbrück, Johannes Köbler, V. Arvind
Publication date: 13 October 2022
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2021.104803
Weisfeiler-Leman algorithmgraph packing problemfractional graph parameterslinear-programming relaxation
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Combinatorial and computational aspects of graph packing and graph decomposition
- Integer and fractional packings in dense graphs
- Definability with bounded number of bound variables
- Approximation hardness of dominating set problems in bounded degree graphs
- On the power of combinatorial and spectral invariants
- Graph isomorphism and theorems of Birkhoff type
- Graphs which contain all small graphs
- Maximum degree and fractional matchings in uniform hypergraphs
- An optimal lower bound on the number of variables for graph identification
- On the ratio of optimal integral and fractional covers
- Fractional isomorphism of graphs
- Pebble games and cospectral graphs
- Matchings and covers in hypergraphs
- Logical hierarchies in PTIME
- Local WL invariance and hidden shades of regularity
- Sherali--Adams Relaxations and Indistinguishability in Counting Logics
- Dimension Reduction via Colour Refinement
- On the Complexity of General Graph Factor Problems
- On recognizing graphs by numbers of homomorphisms
- Solving Linear Programs without Breaking Abstractions
- On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
- Fractional Triangle Decompositions in Graphs with Large Minimum Degree
- Random Graph Isomorphism
- The NP-Completeness of Some Edge-Partition Problems
- Paley graphs satisfy all first-order adjacency axioms
- Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
- Approximations of the domination number of a graph
- Integer and fractional packing of families of graphs
- On polynomial time computation over unordered structures
- Reducibility among Combinatorial Problems
- The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs
- Definable inapproximability: new challenges for duplicator
- Graph isomorphism in quasipolynomial time [extended abstract]
- Finite Model Theory
- On the Weisfeiler-Leman dimension of fractional packing
