MINIMUM FEEDBACK ARC SETS IN ROTATOR AND INCOMPLETE ROTATOR GRAPHS

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)

zbMATH Keywords

generatorefficient algorithmdirected cyclerotator graphfeedback vertex set (FVS)concise formulafeedback arc set (FAS)incomplete rotator graphminimum FASminimum FVS

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

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