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

DOI10.1016/J.DISC.2017.02.012MaRDI QIDQ526233zbMATH OpenOpenAlexFDO

Authors A. P. Figueroa, César Hernández-Cruz, M. Olsen

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

acyclic disconnectionfeedback arc setNP-completenessoriented planar graphs

Mathematics Subject Classification ID

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

Recommendations

• The acyclic disconnection of a digraph
• Minimum feedback vertex set and acyclic coloring.
• On the acyclic disconnection and the girth
• Combinatorial algorithms for feedback problems in directed graphs
• Tight upper bounds for minimum feedback arc sets of regular graphs

Cites work

• A fast and effective heuristic for the feedback arc set problem
• Arc‐Disjoint Cycles and Feedback Arc Sets
• Circulant tournaments of prime order are tight
• Circular colorings of edge-weighted graphs
• scientific article; zbMATH DE number 1764950 (Why is no real title available?)
• On the acyclic disconnection and the girth
• On the acyclic disconnection of multipartite tournaments
• Ranking Tournaments
• The acyclic disconnection of a digraph
• The dichromatic number of a digraph
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Tight upper bounds for minimum feedback arc sets of regular graphs

Cited in

(9)

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

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)