Almost exact minimum feedback vertex set in meshes and butterflies

DOI10.1016/S0020-0190(98)00039-8zbMath0925.68196MaRDI QIDQ1129019

Flaminia L. Luccio

Publication date: 13 August 1998

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

zbMATH Keywords

Algorithms; Mesh; Butterfly; Combinatorial problems; Exact bounds; Feedback vertex set

Mathematics Subject Classification ID

68W10: Parallel algorithms in computer science

Related Items

Feedback numbers of Kautz digraphs, Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies, Feedback numbers of de Bruijn digraphs, An efficient algorithm for minimum feedback vertex sets in rotator graphs, Minimum feedback vertex sets in shuffle-based interconnection networks, Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion, Feedback vertex sets in star graphs, The integrity of a cubic graph, New bounds on the size of the minimum feedback vertex set in meshes and butterflies., Minimum feedback vertex set and acyclic coloring., Solving the feedback vertex set problem on undirected graphs, Feedback vertex sets in mesh-based networks, New upper bounds on feedback vertex numbers in butterflies

Cites Work

• Unnamed Item
• Unnamed Item
• A linear-time algorithm for the weighted feedback vertex problem on interval graphs
• On locating minimum feedback vertex sets
• Size bounds for dynamic monopolies
• On the feedback vertex set problem in permutation graphs
• Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs