Cover Image

Markovian protocols and an upper bound on the extension complexity of the matching polytope

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Szusterman, M.
Format:	Preprint
Published:	2026
Subjects:	Discrete Mathematics Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Deterministic approximation for the volume of the truncated fractional matching polytope
by: Guo, Heng, et al.
Published: (2024)

Clique-free t-matchings in degree-bounded graphs
by: Paluch, Katarzyna, et al.
Published: (2024)

Complexity of polytope diameters via perfect matchings
by: Nöbel, Christian, et al.
Published: (2024)

Triangle-free 2-matchings
by: Paluch, Katarzyna
Published: (2023)

Reconfiguration of labeled matchings in triangular grid graphs
by: Kakimura, Naonori, et al.
Published: (2024)

On the time complexity of finding a well-spread perfect matching in bridgeless cubic graphs
by: Ghanbari, Babak, et al.
Published: (2025)

Traversing combinatorial 0/1-polytopes via optimization
by: Merino, Arturo, et al.
Published: (2023)

Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity
by: Gawrychowski, Paweł, et al.
Published: (2024)

A survey of Chernoff and Hoeffding bounds
by: Gerbessiotis, Alexandros V.
Published: (2025)

Packing $K_r$s in bounded degree graphs
by: McKay, Michael, et al.
Published: (2022)

Near-linear time subhypergraph counting in bounded degeneracy hypergraphs
by: Paul-Pena, Daniel, et al.
Published: (2025)

Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth
by: Foucaud, Florent, et al.
Published: (2025)

Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity
by: Jain, Vishesh, et al.
Published: (2026)

Improved bounds for coloring locally sparse hypergraphs
by: Iliopoulos, Fotis
Published: (2020)

Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
by: Alecu, Bogdan, et al.
Published: (2024)

Quasi-linear distance query reconstruction for graphs of bounded treelength
by: Bastide, Paul, et al.
Published: (2024)

Translating between the representations of an acyclic convex geometry of bounded degree
by: Defrain, Oscar, et al.
Published: (2025)

Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
by: Bonamy, Marthe, et al.
Published: (2020)

Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
by: Bencs, Ferenc, et al.
Published: (2025)

Separable convex optimization over indegree polytopes
by: Borsik, Nóra A., et al.
Published: (2025)

Parameterized complexity of isometric path partition: treewidth and diameter
by: Chakraborty, Dibyayan, et al.
Published: (2025)

Improved bounds for the zeros of the chromatic polynomial via Whitney's Broken Circuit Theorem
by: Jenssen, Matthew, et al.
Published: (2023)

On the complexity of finding a spanning even tree in a graph
by: Hanaka, Tesshu, et al.
Published: (2024)

Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?
by: Chakraborty, Dibyayan, et al.
Published: (2024)

Online Graph Balancing and the Power of Two Choices
by: Bansal, Nikhil, et al.
Published: (2026)

Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
by: Disser, Yann, et al.
Published: (2024)

H-Planarity and Parametric Extensions: when Modulators Act Globally
by: Fomin, Fedor V., et al.
Published: (2025)

Graph Visualization for Blockchain Data
by: Dietl, Marcell, et al.
Published: (2024)

Fast Makespan Minimization via Short ILPs
by: Hermelin, Danny, et al.
Published: (2026)

A Unified Approach to Minimizing Symmetric Submodular Functions
by: Iwata, Satoru, et al.
Published: (2026)

Optimal Enumeration of Eulerian Trails in Directed Graphs
by: Bals, Ben, et al.
Published: (2026)

Parameterized Local Search for Vertex Cover: When only the Search Radius is Crucial
by: Komusiewicz, Christian, et al.
Published: (2026)

Minimum Sum Set Cover: Structures and Algorithm
by: Zhang, Zhongyi, et al.
Published: (2026)

Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs
by: Abbasi, Ali, et al.
Published: (2026)

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
by: Foucaud, Florent, et al.
Published: (2026)

Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
by: German, Samuel
Published: (2026)

Fanciful Figurines flip Free Flood-It -- Polynomial-Time Miniature Painting on Co-gem-free Graphs
by: Rosenke, Christian, et al.
Published: (2026)

Node-Weighted Triangles: Faster and Simpler
by: Akmal, Shyan, et al.
Published: (2026)

Terminal Steiner tree problem : Complexity and Algorithms
by: S, Jyothish, et al.
Published: (2026)

Near-Optimal Constructive Bounds for $\ell_2$ Prefix Discrepancy and Steinitz Problems via Affine Spectral Independence
by: Dutta, Kunal, et al.
Published: (2026)