Networks with unicyclic connected components and without short cycles

Walid Ben-Ameur; Makhlouf Hadji; Adam Ouorou

doi:10.1016/j.endm.2010.05.122

Networks with unicyclic connected components and without short cycles

Walid Ben-Ameur
, Makhlouf Hadji
, Adam Ouorou

Telecom Sudparis
Orange Labs

Research output: Contribution to journal › Article › peer-review

Abstract

This paper focuses on the design of networks with unicyclic connected components. The size of each cycle should not be less than a given number. A polyhedral study is proposed. Many facets and valid inequalities are derived. Some of them can be exactly separated in polynomial time. Then the network design problem is solved by a cutting plane algorithm based on these inequalities and using a compact formulation issued from the transversality of the bicircular matroid.

Original language	English
Pages (from-to)	961-968
Number of pages	8
Journal	Electronic Notes in Discrete Mathematics
Volume	36
Issue number	C
DOIs	https://doi.org/10.1016/j.endm.2010.05.122
Publication status	Published - 1 Aug 2010

Keywords

Bicircular matroid
Cycles
Networks
Polyhedra

Access to Document

10.1016/j.endm.2010.05.122

Cite this

@article{8f6d6f15c21c4e93b417dd8a35b07b3a,

title = "Networks with unicyclic connected components and without short cycles",

abstract = "This paper focuses on the design of networks with unicyclic connected components. The size of each cycle should not be less than a given number. A polyhedral study is proposed. Many facets and valid inequalities are derived. Some of them can be exactly separated in polynomial time. Then the network design problem is solved by a cutting plane algorithm based on these inequalities and using a compact formulation issued from the transversality of the bicircular matroid.",

keywords = "Bicircular matroid, Cycles, Networks, Polyhedra",

author = "Walid Ben-Ameur and Makhlouf Hadji and Adam Ouorou",

year = "2010",

month = aug,

day = "1",

doi = "10.1016/j.endm.2010.05.122",

language = "English",

volume = "36",

pages = "961--968",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier B.V.",

number = "C",

}

TY - JOUR

T1 - Networks with unicyclic connected components and without short cycles

AU - Ben-Ameur, Walid

AU - Hadji, Makhlouf

AU - Ouorou, Adam

PY - 2010/8/1

Y1 - 2010/8/1

N2 - This paper focuses on the design of networks with unicyclic connected components. The size of each cycle should not be less than a given number. A polyhedral study is proposed. Many facets and valid inequalities are derived. Some of them can be exactly separated in polynomial time. Then the network design problem is solved by a cutting plane algorithm based on these inequalities and using a compact formulation issued from the transversality of the bicircular matroid.

AB - This paper focuses on the design of networks with unicyclic connected components. The size of each cycle should not be less than a given number. A polyhedral study is proposed. Many facets and valid inequalities are derived. Some of them can be exactly separated in polynomial time. Then the network design problem is solved by a cutting plane algorithm based on these inequalities and using a compact formulation issued from the transversality of the bicircular matroid.

KW - Bicircular matroid

KW - Cycles

KW - Networks

KW - Polyhedra

U2 - 10.1016/j.endm.2010.05.122

DO - 10.1016/j.endm.2010.05.122

M3 - Article

AN - SCOPUS:77954907427

SN - 1571-0653

VL - 36

SP - 961

EP - 968

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

IS - C

ER -

Networks with unicyclic connected components and without short cycles

Abstract

Keywords

Access to Document

Fingerprint

Cite this