Lehman's Theorem and the Directed Steiner Tree Problem

DOI10.1137/15M1007185zbMath1336.90107OpenAlexW2238259313MaRDI QIDQ3462549

Ahmad Abdi, Guenin, Bertrand, Laura Sanità, Jochen Könemann, Andreas Emil Feldmann

Publication date: 15 January 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/15m1007185

zbMATH Keywords

integral polyhedraset covering polyhedronLehman's theoremideal cluttersdirected Steiner trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items (3)

Clearing directed subgraphs by mobile agents. Variations on covering with paths ⋮ Opposite Elements in Clutters ⋮ Resistant Sets in the Unit Hypercube

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A class of simple games
• Lehman matrices
• Arborescence polytopes for series-parallel graphs
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• A characterization of weakly bipartite graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Applying Lehman's theorems to packing problems
• Topology of series-parallel networks
• Combinatorial designs and related systems
• Global Optimization with Polynomials and the Problem of Moments
• Integer Programming
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Maximal Flow Through a Network
• Polylogarithmic inapproximability
• On the width—length inequality
• Cones of Matrices and Set-Functions and 0–1 Optimization
• The Forbidden Minors of Binary Clutters
• Packing rooted directed cuts in a weighted directed graph
• Approximation Algorithms for Directed Steiner Problems
• Linear Programming Hierarchies Suffice for Directed Steiner Tree
• A Solution of the Shannon Switching Game
• Optimum branchings
• Bottleneck extrema
• Blocking and anti-blocking pairs of polyhedra
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• The packing property.

This page was built for publication: Lehman's Theorem and the Directed Steiner Tree Problem