Minimal arc-sets spanning dicycles

Cornaz, Denis; Kerivin, Hervé; Mahjoub, Ali Ridha

Cornaz, Denis; Kerivin, Hervé; Mahjoub, Ali Ridha (2018), Minimal arc-sets spanning dicycles, Discrete Applied Mathematics, 240, 1, p. 33-43. 10.1016/j.dam.2017.02.011

Type

Article accepté pour publication ou publié

Date

2018

Journal name

Discrete Applied Mathematics

Volume

240

Number

Publisher

Elsevier

Pages

33-43

Publication identifier

10.1016/j.dam.2017.02.011

Metadata

Show full item record

Author(s)

Cornaz, Denis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Kerivin, Hervé
Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes [LIMOS]
Mahjoub, Ali Ridha

Abstract (EN)

We give a structural characterization of the inclusionwise minimal arc subsets whose vertices induce a subgraph containing at least one directed cycle. These arc sets arise in a linear formulation of a binary quadratic problem.

Subjects / Keywords

Directed cycles; Minimal forbidden structure; Sherali-Adams’s Linearization; 0–1 programming