NDLI: On the Polytope of the (1,2)-Survivable Network Design Problem

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Kerivin, Herv Mahjoub, A. Ridha Biha, Mohamed Didi
Copyright Year	2008
Abstract	This paper deals with the survivable network design problem where each node v has a connectivity type $r(v)$ equal to 1 or 2, and the survivability conditions require the existence of at least $\min\{r(s),r(t)\}$ edge-disjoint paths for all distinct nodes s and t. We consider the polytope given by the trivial and cut inequalities together with the partition inequalities. More precisely, we study some structural properties of this polytope which leads us to give some sufficient conditions for this polytope to be integer in the class of series-parallel graphs. With both separation problems for the cut and partition inequalities being polynomially solvable, we then obtain a polynomial time algorithm for the (1,2)-survivable network design problem in a subclass of series-parallel graphs including the outerplanar graph class. We also introduce a new class of facet-defining inequalities for the polytope associated to the (1,2)-survivable network design problem.
Starting Page	1640
Ending Page	1666
Page Count	27
File Format	PDF
ISSN	08954801
DOI	10.1137/050639600
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	4
Volume Number	22
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2008-10-17
Access Restriction	Subscribed
Subject Keyword	cut and partition inequalities Integer programming survivable network Network design and communication facet series-parallel graphs polytope Polyhedral combinatorics, branch-and-bound, branch-and-cut
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On the Graph Bisection Cut Polytope

Generating Facets for the Independence System Polytope

On the Facet-Inducing Antiweb-Wheel Inequalities for Stable Set Polytopes

Facets of the Weak Order Polytope Derived from the Induced Partition Projection

Survivable network design using polyhedral approaches

On the connected (sub)partition polytope

The stable set polytope of quasi-line graphs

The st-bond polytope on series-parallel graphs

On the Sequential Multiknapsack polytope

On the Polytope of the (1,2)-Survivable Network Design Problem

Similar Documents

On the Graph Bisection Cut Polytope

Generating Facets for the Independence System Polytope

On the Facet-Inducing Antiweb-Wheel Inequalities for Stable Set Polytopes

Facets of the Weak Order Polytope Derived from the Induced Partition Projection

Survivable network design using polyhedral approaches

On the connected (sub)partition polytope

The stable set polytope of quasi-line graphs

The st-bond polytope on series-parallel graphs

On the Sequential Multiknapsack polytope

On the Polytope of the (1,2)-Survivable Network Design Problem