Minimal arc-sets spanning dicycles

DOI10.1016/J.DAM.2017.02.011MaRDI QIDQ1707911zbMATH OpenOpenAlexFDO

Authors Denis Cornaz, Hervé L. M. Kerivin, A. R. Mahjoub

Publication date 4 April 2018

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

Full work available at URL https://doi.org/10.1016/j.dam.2017.02.011

zbMATH Keywords

0-1 programmingdirected cyclesminimal forbidden structureSherali-Adams's linearization

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Linear programming (90C05)

Recommendations

• Directed cycles with two chords and strong spanning directed subgraphs with few arcs
• Facets of the p-cycle polytope
• On digraphs with no two disjoint directed cycles
• Strongly Connected Spanning Subdigraphs with the Minimum Number of Arcs in Quasi-transitive Digraphs
• An exact method for the minimum feedback arc set problem

Cites work

• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• Chromatic characterization of biclique covers
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Cones of Matrices and Set-Functions and 0–1 Optimization
• scientific article; zbMATH DE number 1757962 (Why is no real title available?)
• Improved Linear Integer Programming Formulations of Nonlinear Integer Problems
• Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
• The ellipsoid method and its consequences in combinatorial optimization
• The Maximum Induced Bipartite Subgraph Problem with Edge Weights

Cited in

(2)

• Arc‐Disjoint Cycles and Feedback Arc Sets
• A characterization of positive spanning sets with ties to strongly edge-connected digraphs

This page was built for publication: Minimal arc-sets spanning dicycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1707911)