Minimum feedback arc sets in rotator and incomplete rotator graphs

DOI10.1142/S0129054112500116zbMATH Open1254.05188MaRDI QIDQ4902886FDOQ4902886

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)

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

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)

Cites Work

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

Cited In (4)

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

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)