Finding a minimum feedback arc set in reducible flow graphs

DOI10.1016/0196-6774(88)90022-3zbMath0651.68082OpenAlexW2953534551MaRDI QIDQ3796774

Vijaya Ramachandran

Publication date: 1988

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(88)90022-3

zbMATH Keywords

reducible flow graphsflow networksminimum weight feedback arc set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (11)

More facets from fences for linear ordering and acyclic subgraph polytopes ⋮ Approximations for the maximum acyclic subgraph problem ⋮ Packing feedback arc sets in reducible flow graphs ⋮ The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem ⋮ An Exact Method for the Minimum Feedback Arc Set Problem ⋮ Solving problems for maximal reducible flowgraphs. ⋮ MINIMUM FEEDBACK ARC SETS IN ROTATOR AND INCOMPLETE ROTATOR GRAPHS ⋮ A \(\min\)-\(\max\) relation in flowgraphs and some applications ⋮ Exact localisations of feedback sets ⋮ Unnamed Item ⋮ Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs

This page was built for publication: Finding a minimum feedback arc set in reducible flow graphs