Minimum feedback arc sets in rotator and incomplete rotator graphs

DOI10.1142/S0129054112500116MaRDI QIDQ4902886zbMATH OpenFDO

Authors Chi-Jung Kuo, Chiun-Chieh Hsu, Hon-Ren Lin, Da-Ren Chen

Publication date 18 January 2013

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

generatordirected cycleefficient algorithmrotator graphfeedback vertex set (FVS)concise formulafeedback arc set (FAS)incomplete rotator graphminimum FASminimum FVS

Mathematics Subject Classification ID

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

Recommendations

• An efficient algorithm for minimum feedback vertex sets in rotator graphs
• Feedback Vertex Sets in Rotator Graphs
• A fast and effective heuristic for the feedback arc set problem
• scientific article; zbMATH DE number 219267
• Exact localisations of feedback sets

Cites work

• scientific article; zbMATH DE number 43081 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A fast and effective algorithm for the feedback arc set problem
• A fast and effective heuristic for the feedback arc set problem
• Almost exact minimum feedback vertex set in meshes and butterflies
• An efficient algorithm for minimum feedback vertex sets in rotator graphs
• Approximating minimum feedback sets and multicuts in directed graphs
• Approximation algorithms for combinatorial problems
• Exact and heuristic algorithms for the weighted feedback arc set problem: A special case of the skew-symmetric quadratic assignment problem
• Feedback Vertex Sets in Rotator Graphs
• Feedback vertex set in hypercubes
• Feedback vertex sets in star graphs
• Finding a minimum feedback arc set in reducible flow graphs
• Linear programming based approximation algorithms for feedback set problems in bipartite tournaments
• Minimal feedback vertex sets in directed split‐stars
• Minimum feedback vertex sets in shuffle-based interconnection networks
• New bounds on the size of the minimum feedback vertex set in meshes and butterflies.
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments

Cited in

(4)

• Arc‐Disjoint Cycles and Feedback Arc Sets
• An efficient algorithm for minimum feedback vertex sets in rotator graphs
• Feedback Vertex Sets in Rotator Graphs
• Finding a minimum feedback arc set in reducible flow graphs

This page was built for publication: Minimum feedback arc sets in rotator and incomplete rotator graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4902886)