MINIMUM FEEDBACK ARC SETS IN ROTATOR AND INCOMPLETE ROTATOR GRAPHS
From MaRDI portal
Publication:4902886
DOI10.1142/S0129054112500116zbMath1254.05188MaRDI QIDQ4902886
Chi-Jung Kuo, Da-Ren Chen, Chiun-Chieh Hsu, Hon-Ren Lin
Publication date: 18 January 2013
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
generator; efficient algorithm; directed cycle; rotator graph; feedback vertex set (FVS); concise formula; feedback arc set (FAS); incomplete rotator graph; minimum FAS; minimum FVS
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
Cites Work
- Unnamed Item
- Unnamed Item
- Feedback vertex set in hypercubes
- Linear programming based approximation algorithms for feedback set problems in bipartite tournaments
- A fast and effective heuristic for the feedback arc set problem
- An efficient algorithm for minimum feedback vertex sets in rotator graphs
- Minimum feedback vertex sets in shuffle-based interconnection networks
- Feedback vertex sets in star graphs
- Almost exact minimum feedback vertex set in meshes and butterflies
- Approximation algorithms for combinatorial problems
- Approximating minimum feedback sets and multicuts in directed graphs
- New bounds on the size of the minimum feedback vertex set in meshes and butterflies.
- Exact and heuristic algorithms for the weighted feedback arc set problem: A special case of the skew-symmetric quadratic assignment problem
- The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
- Feedback Vertex Sets in Rotator Graphs
- Finding a minimum feedback arc set in reducible flow graphs
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Minimal feedback vertex sets in directed split‐stars
- A fast and effective algorithm for the feedback arc set problem
