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

DOI10.1016/J.DISC.2017.02.012zbMATH Open1361.05047OpenAlexW2603633312MaRDI QIDQ526233FDOQ526233

M. Olsen, A. P. 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-completenessfeedback arc setacyclic disconnectionoriented planar graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cites Work

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

Cited In (6)

• Finding a minimum feedback arc set in reducible flow graphs
• A family of bipartite circulant tournaments with acyclic disconnection 3
• Bounds on the acyclic disconnection of a digraph
• The connection of the acyclic disconnection and feedback arc sets -- on an open problem of Figueroa et al..
• Feedback arc number and feedback vertex number of Cartesian product of directed cycles
• Arc‐Disjoint Cycles and Feedback Arc Sets

This page was built for publication: The minimum feedback arc set problem and the acyclic disconnection for graphs

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