An efficient algorithm for minimum feedback vertex sets in rotator graphs

DOI10.1016/J.IPL.2009.01.004MaRDI QIDQ987789zbMATH OpenOpenAlexFDO

Authors Chi-Jung Kuo, Chiun-Chieh Hsu, Hon-Ren Lin, Kung-Kuei Lin

Publication date 16 August 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2009.01.004

zbMATH Keywords

generatorgraph algorithmscyclefeedback vertex setrotator graph

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

• Feedback Vertex Sets in Rotator Graphs
• Minimum feedback arc sets in rotator and incomplete rotator graphs
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Minimal feedback vertex sets in directed split‐stars
• Faster fixed parameter tractable algorithms for finding feedback vertex sets

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Graph Theoretic Approach to Statistical Data Security
• Almost exact minimum feedback vertex set in meshes and butterflies
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• 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
• Minimum feedback vertex sets in shuffle-based interconnection networks
• New bounds on the size of the minimum feedback vertex set in meshes and butterflies.
• Node-Deletion Problems on Bipartite Graphs

Cited in

(6)

• Feedback vertex sets on restricted bipartite graphs
• Minimum feedback arc sets in rotator and incomplete rotator graphs
• Feedback Vertex Sets in Rotator Graphs
• Domination number and feedback vertex number of complements of line graphs
• Feedback arc number and feedback vertex number of Cartesian product of directed cycles
• Two Hardness Results on Feedback Vertex Sets

This page was built for publication: An efficient algorithm for minimum feedback vertex sets in rotator graphs

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