Constant-factor LP-based approximation for Max Dist-2 Independent Set (and Min Dominating Set) in bounded radius-2 merge-width graphs, with the domination-to-2-independence ratio shown bounded and tight for radius-1.
χ-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
years
2026 2verdicts
UNVERDICTED 2representative citing papers
Graphs admitting Welzl orders with sublinear-interval neighborhoods have small biclique decompositions, yielding log-factor extensions to bounds on Zarankiewicz, matrix multiplication, quantum circuits, and structured shortest paths.
citing papers explorer
-
Constant-factor approximation of maximum distance-2 independent set in graphs of bounded merge-width
Constant-factor LP-based approximation for Max Dist-2 Independent Set (and Min Dominating Set) in bounded radius-2 merge-width graphs, with the domination-to-2-independence ratio shown bounded and tight for radius-1.
-
Biclique decompositions from Welzl orders
Graphs admitting Welzl orders with sublinear-interval neighborhoods have small biclique decompositions, yielding log-factor extensions to bounds on Zarankiewicz, matrix multiplication, quantum circuits, and structured shortest paths.