An efficient algorithm for minimum feedback vertex sets in rotator graphs

DOI10.1016/j.ipl.2009.01.004zbMath1209.68378OpenAlexW1992661305MaRDI QIDQ987789

Chiun-Chieh Hsu, Hon-Ren Lin, Chi-Jung Kuo, 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

generatorcyclegraph algorithmsfeedback vertex setrotator graph

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)

Related Items (5)

Feedback vertex sets on restricted bipartite graphs ⋮ Domination number and feedback vertex number of complements of line graphs ⋮ Two Hardness Results on Feedback Vertex Sets ⋮ MINIMUM FEEDBACK ARC SETS IN ROTATOR AND INCOMPLETE ROTATOR GRAPHS ⋮ Feedback arc number and feedback vertex number of Cartesian product of directed cycles

Cites Work

• Unnamed Item
• Feedback vertex set in hypercubes
• 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
• 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
• Feedback Vertex Sets in Rotator Graphs
• A Graph Theoretic Approach to Statistical Data Security
• Node-Deletion Problems on Bipartite Graphs
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference

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