A fast and effective heuristic for the feedback arc set problem

DOI10.1016/0020-0190(93)90079-OzbMATH Open0787.68078OpenAlexW2058702778WikidataQ59650036 ScholiaQ59650036MaRDI QIDQ688447FDOQ688447

Authors: Peter Eades, Xuemin Lin, W. F. Smyth 

Publication date: 19 May 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90079-o

Recommendations

• scientific article; zbMATH DE number 825126
• An exact method for the minimum feedback arc set problem
• Finding a minimum feedback arc set in reducible flow graphs
• scientific article; zbMATH DE number 139781
• Tight localizations of feedback sets

zbMATH Keywords

data structuredigraphfeedback arc setconnected directed graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Title not available (Why is that?)
• On Sets of Consistent Arcs in a Tournament
• Title not available (Why is that?)
• Optimally ranking unrankable tournaments
• Title not available (Why is that?)
• Optimal ranking of tournaments
• On the maximum cardinality of a consistent set of arcs in a random tournament

Cited In (29)

• Modeling the emergence of modular leadership hierarchy during the collective motion of herds made of harems
• Tight localizations of feedback sets
• Title not available (Why is that?)
• Combinatorial algorithms for feedback problems in directed graphs
• Approximations of arbitrary relations by partial orders
• The network HHD: quantifying cyclic competition in trait-performance models of tournaments
• Exact localisations of feedback sets
• Compact layered drawings of general directed graphs
• A fast and effective algorithm for the feedback arc set problem
• Efficient mode enumeration of compositional hybrid systems
• Effective Computation of a Feedback Arc Set Using PageRank
• Feedback arc set. A history of the problem and algorithms
• A generalization of the directed graph layering problem
• Minimum feedback arc sets in rotator and incomplete rotator graphs
• An updated survey on the linear ordering problem for weighted or unweighted tournaments
• An exact method for the minimum feedback arc set problem
• Exact and heuristic algorithms for the weighted feedback arc set problem: A special case of the skew-symmetric quadratic assignment problem
• Analysis of the equality relations for the program terms
• Balanced vertex-orderings of graphs
• Efficient heuristics to compute minimal and stable feedback arc sets
• Optimal segmentation of directed graph and the minimum number of feedback arcs
• A survey on the linear ordering problem for weighted or unweighted tournaments
• Computing a feedback arc set using PageRank
• Title not available (Why is that?)
• Title not available (Why is that?)
• Extremal results on feedback arc sets in digraphs
• Title not available (Why is that?)
• Comments on “An Exact Method for the Minimum Feedback Arc Set Problem”
• The minimum feedback arc set problem and the acyclic disconnection for graphs

This page was built for publication: A fast and effective heuristic for the feedback arc set problem

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