Combinatorial algorithms for feedback problems in directed graphs

DOI10.1016/S0020-0190(02)00491-XzbMath1173.68586OpenAlexW1980481456MaRDI QIDQ1007586

Camil Demetrescu, Irene Finocchi

Publication date: 23 March 2009

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00491-x

zbMATH Keywords

combinatorial optimizationdirected graphsapproximation algorithmsfeedback problems

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (6)

An Exact Method for the Minimum Feedback Arc Set Problem ⋮ The difficulty of beating the Taxman ⋮ Computation of Renameable Horn Backdoors ⋮ Controlled perturbation of sets of line segments in \(\mathbb R^2\) with smart processing order ⋮ Capacity inverse minimum cost flow problem ⋮ Clique Counting in MapReduce

Cites Work

• A fast and effective heuristic for the feedback arc set problem
• Approximations for the maximum acyclic subgraph problem
• On enumerating all minimal solutions of feedback problems
• Packing directed circuits fractionally
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• Exact and heuristic algorithms for the weighted feedback arc set problem: A special case of the skew-symmetric quadratic assignment problem
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Combinatorial algorithms for feedback problems in directed graphs