Tight Localizations of Feedback Sets

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

zbMATH Keywords

approximation algorithmminimum feedback arc set problemminimum feedback vertex set problemmaximum linear ordering problem

Mathematics Subject Classification ID

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

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