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

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

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.

langue originale	Anglais
Pages (de - à)	961-968
Nombre de pages	8
journal	Electronic Notes in Discrete Mathematics
Volume	36
Numéro de publication	C
Les DOIs	https://doi.org/10.1016/j.endm.2010.05.122
état	Publié - 1 août 2010

Accès au document

10.1016/j.endm.2010.05.122

Contient cette citation

@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

Résumé

Accès au document

Empreinte digitale

Contient cette citation