Tight Localizations of Feedback Sets
From MaRDI portal
Publication:5102049
DOI10.1145/3447652zbMath1499.68276arXiv2001.01440OpenAlexW3142463313MaRDI QIDQ5102049
Krzysztof Gonciarz, Michael Hecht, Szabolcs Horvát
Publication date: 6 September 2022
Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2001.01440
approximation algorithmminimum feedback arc set problemminimum feedback vertex set problemmaximum linear ordering problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The linear ordering problem. Exact and heuristic methods in combinatorial optimization.
- A fast and effective heuristic for the feedback arc set problem
- Exact localisations of feedback sets
- On the hardness of approximating minimum vertex cover
- Retiming synchronous circuitry
- Structure preserving reductions among convex optimization problems
- Edge-disjoint spanning trees and depth-first search
- Approximations for the maximum acyclic subgraph problem
- Approximating minimum feedback sets and multicuts in directed graphs
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Improved Deterministic Algorithms for Decremental Reachability and Strongly Connected Components
- Exact and heuristic algorithms for the weighted feedback arc set problem: A special case of the skew-symmetric quadratic assignment problem
- Topological sorting of large networks
- A fixed-parameter algorithm for the directed feedback vertex set problem
- On the acyclic subgraph polytope
- A new approach to the maximum-flow problem
- A Minimax Theorem for Directed Graphs
- A Faster Deterministic Maximum Flow Algorithm
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Reducibility among Combinatorial Problems
- Computational Complexity
- Collective dynamics of ‘small-world’ networks
- Ranking tournaments
- Max flows in O(nm) time, or better
- Depth-First Search and Linear Graph Algorithms
- A fast and effective algorithm for the feedback arc set problem
This page was built for publication: Tight Localizations of Feedback Sets