The minimum feedback arc set problem and the acyclic disconnection for graphs

DOI10.1016/j.disc.2017.02.012zbMath1361.05047MaRDI QIDQ526233

Mika Olsen, Ana Paulina Figueroa, César Hernández-Cruz

Publication date: 10 May 2017

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

Full work available at URL: https://doi.org/10.1016/j.disc.2017.02.012

zbMATH Keywords

NP-completeness; feedback arc set; acyclic disconnection; oriented planar graphs

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C10: Planar graphs; geometric and topological aspects of graph theory

05C15: Coloring of graphs and hypergraphs

Related Items

A family of bipartite circulant tournaments with acyclic disconnection 3, Feedback arc number and feedback vertex number of Cartesian product of directed cycles

Cites Work

• Unnamed Item
• On the acyclic disconnection of multipartite tournaments
• A fast and effective heuristic for the feedback arc set problem
• Circulant tournaments of prime order are tight
• The acyclic disconnection of a digraph
• The dichromatic number of a digraph
• On the acyclic disconnection and the girth
• Tight Upper Bounds for Minimum Feedback Arc Sets of Regular Graphs
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Circular colorings of edge-weighted graphs
• Arc‐Disjoint Cycles and Feedback Arc Sets
• Ranking Tournaments