Minimum feedback vertex sets in shuffle-based interconnection networks

DOI10.1016/S0020-0190(02)00504-5zbMATH Open1173.68590OpenAlexW1982420787MaRDI QIDQ1007599FDOQ1007599

Authors: 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

Recommendations

• Feedback vertex sets in mesh-based networks
• Feedback vertex set in hypercubes
• Structural Information and Communication Complexity
• Minimal feedback vertex sets in directed split‐stars
• The feedback number of crossed cube networks

zbMATH Keywords

combinatorial problemsfeedback vertex setde BruijnKautzshuffle exchange

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

Cites Work

• Title not available (Why is that?)
• Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Title not available (Why is that?)
• On the feedback vertex set problem in permutation graphs
• A linear-time algorithm for the weighted feedback vertex problem on interval graphs
• Almost exact minimum feedback vertex set in meshes and butterflies
• Decycling hypercubes
• Feedback vertex set in hypercubes
• 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
• Decycling cubes and grids

Cited In (12)

• The feedback number of crossed cube networks
• An efficient algorithm for minimum feedback vertex sets in rotator graphs
• New upper bounds on feedback vertex numbers in butterflies
• Feedback vertex set in hypercubes
• Feedback vertex sets on restricted bipartite graphs
• Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies
• Minimum feedback arc sets in rotator and incomplete rotator graphs
• Feedback vertex sets in mesh-based networks
• Structural Information and Communication Complexity
• Feedback numbers of Kautz digraphs
• Feedback numbers of de Bruijn digraphs
• Two Hardness Results on Feedback Vertex Sets

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

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