Minimum feedback vertex sets in shuffle-based interconnection networks

DOI10.1016/S0020-0190(02)00504-5zbMath1173.68590OpenAlexW1982420787MaRDI QIDQ1007599

Rastislav Královič, Peter Ružička

Publication date: 23 March 2009

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00504-5

zbMATH Keywords

combinatorial problemsfeedback vertex setde BruijnKautzshuffle exchange

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

Related Items (8)

Feedback vertex sets in mesh-based networks ⋮ New upper bounds on feedback vertex numbers in butterflies ⋮ Feedback numbers of Kautz digraphs ⋮ Feedback vertex sets on restricted bipartite graphs ⋮ Two Hardness Results on Feedback Vertex Sets ⋮ MINIMUM FEEDBACK ARC SETS IN ROTATOR AND INCOMPLETE ROTATOR GRAPHS ⋮ Feedback numbers of de Bruijn digraphs ⋮ An efficient algorithm for minimum feedback vertex sets in rotator graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for the weighted feedback vertex problem on interval graphs
• Feedback vertex set in hypercubes
• Almost exact minimum feedback vertex set in meshes and butterflies
• On the feedback vertex set problem in permutation graphs
• Decycling hypercubes
• Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
• Feedback vertex sets and cyclically reducible graphs
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Decycling graphs
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem

This page was built for publication: Minimum feedback vertex sets in shuffle-based interconnection networks