Combinatorial algorithms for feedback problems in directed graphs

DOI10.1016/S0020-0190(02)00491-XzbMATH Open1173.68586OpenAlexW1980481456MaRDI QIDQ1007586FDOQ1007586

Authors: 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

Recommendations

• Approximating minimum feedback sets and multi-cuts in directed graphs (extended summary)
• Approximating minimum feedback sets and multicuts in directed graphs
• scientific article; zbMATH DE number 3876618
• Exact localisations of feedback sets
• scientific article; zbMATH DE number 825126

zbMATH Keywords

combinatorial optimizationapproximation algorithmsdirected graphsfeedback problems

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• Title not available (Why is that?)
• Packing directed circuits fractionally
• On enumerating all minimal solutions of feedback problems
• Approximations for the maximum acyclic subgraph problem
• A fast and effective heuristic for the feedback arc set problem
• Title not available (Why is that?)
• Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
• Exact and heuristic algorithms for the weighted feedback arc set problem: A special case of the skew-symmetric quadratic assignment problem
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (24)

• Optimal schemes for combinatorial query problems with integer feedback
• Computation of Renameable Horn Backdoors
• Controlled perturbation of sets of line segments in \(\mathbb R^2\) with smart processing order
• Tight upper bounds for minimum feedback arc sets of regular graphs
• Parallelism and the feedback vertex set problem
• Approximating minimum feedback sets and multi-cuts in directed graphs (extended summary)
• Title not available (Why is that?)
• The difficulty of beating the Taxman
• On the complexity of feedback set problems in signed digraphs
• The feedback arc set problem with triangle inequality is a vertex cover problem
• 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
• Clique counting in MapReduce: algorithms and experiments
• Title not available (Why is that?)
• The Minimal Feedback Arc Set Problems^*
• The feedback arc set problem with triangle inequality is a vertex cover problem
• Optimal segmentation of directed graph and the minimum number of feedback arcs
• On enumerating all minimal solutions of feedback problems
• Title not available (Why is that?)
• DTCPP - A heuristic program for testing decyclization in directed graphs and its isomorphic image by using combinatorial approach
• Capacity inverse minimum cost flow problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• The minimum feedback arc set problem and the acyclic disconnection for graphs

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

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