Polyhedral study of the connected subgraph problem

DOI10.1016/J.DISC.2014.08.026zbMath1301.05232OpenAlexW1979589380MaRDI QIDQ468440

Hervé L. M. Kerivin, Peh H. Ng, Mohamed Didi Biha

Publication date: 7 November 2014

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

Full work available at URL: https://doi.org/10.1016/j.disc.2014.08.026

zbMATH Keywords

partitionmatchingpolytopeseparationconnected subgraph

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Connectivity (05C40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (5)

On imposing connectivity constraints in integer programs ⋮ Optimal connected subgraphs: Integer programming formulations and polyhedra ⋮ Vertex covering with capacitated trees ⋮ Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem ⋮ A computational study on the maximum-weight bounded-degree rooted tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Geometric algorithms and combinatorial optimization
• The Steiner tree polytope and related polyhedra
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• The Steiner tree problem. II: Properties and classes of facets
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A new approach to the maximum-flow problem
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• The Complexity of Multiterminal Cuts
• A General Approximation Technique for Constrained Forest Problems
• Steiner trees and polyhedra
• Sharing the cost of multicast transmissions

This page was built for publication: Polyhedral study of the connected subgraph problem