On a class of strong valid inequalities for the connected matching polytope

We identify a family of \(O(|E(G)|^2)\) nontrivial facets of the connected matching polytope of a graph \(G\), that is, the convex hull of incidence vectors of matchings in \(G\) whose covered vertices induce a connected subgraph. Accompanying software to further inspect the polytope of an input gra...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-10
Main Author: Phillippe Samer
Format: Article
Language:English
Subjects:
Apexes
Convexity
Graph theory
Matching
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We identify a family of \(O(|E(G)|^2)\) nontrivial facets of the connected matching polytope of a graph \(G\), that is, the convex hull of incidence vectors of matchings in \(G\) whose covered vertices induce a connected subgraph. Accompanying software to further inspect the polytope of an input graph is available.
ISSN:2331-8422