Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

DOI10.1137/19M1290802zbMath1499.68367arXiv1708.02222OpenAlexW3141846633MaRDI QIDQ5858649

Rohit Gurjar, Nisheeth K. Vishnoi, Thomas Thierauf

Publication date: 14 April 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

derandomizationtotally unimodularisolation lemmaregular matroidsshort lattice vectorsbox-TDI polytopes

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (4)

Polyhedral techniques in combinatorial optimization: matchings and tours ⋮ NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs ⋮ Bipartite Perfect Matching is in Quasi-NC ⋮ On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes)

Uses Software

• Leibniz

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial bound on the number of light cycles in an undirected graph
• Nonlinear discrete optimization. An algorithmic theory
• Matching is as easy as matrix inversion
• A decomposition theory for matroids. V: Testing of matrix total unimodularity
• Decomposition of regular matroids
• Coflow polyhedra
• Kuratowski's and Wagner's theorems for matroids
• Matching and multidimensional matching in chordal and strongly chordal graphs
• On box-perfect graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Cycle cover ratio of regular matroids
• Deterministically isolating a perfect matching in bipartite planar graphs
• Lattices with exponentially large kissing numbers
• Directed Planar Reachability Is in Unambiguous Log-Space
• Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
• The Polynomially Bounded Perfect Matching Problem Is in NC 2
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• On Chebyshev-Type Inequalities for Primes
• The number of shortest cycles and the chromatic uniqueness of a graph
• Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arborescences and Edge-Disjoint Spanning Trees
• Making Nondeterminism Unambiguous
• Linear matroid intersection is in quasi-NC
• Shortest Two Disjoint Paths in Polynomial Time
• On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes)
• Entropy, optimization and counting
• Bipartite perfect matching is in quasi-NC
• A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid

This page was built for publication: Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces