Almost exact minimum feedback vertex set in meshes and butterflies

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

Flaminia L. Luccio

Publication date: 13 August 1998

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(98)00039-8

zbMATH Keywords

AlgorithmsMeshButterflyCombinatorial problemsExact boundsFeedback vertex set

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Related Items (28)

The size of graphs with given feedback vertex number ⋮ Feedback vertex set in hypercubes ⋮ A feedback vertex set of 2-degenerate graphs ⋮ Feedback vertex sets in mesh-based networks ⋮ New upper bounds on feedback vertex numbers in butterflies ⋮ The decycling number of $P_{m} \square P_{n}^{\ast}$ ⋮ Decycling bipartite graphs ⋮ Feedback numbers of Kautz digraphs ⋮ Feedback vertex sets on restricted bipartite graphs ⋮ Target set selection on generalized pancake graphs ⋮ Dynamic monopolies and feedback vertex sets in hexagonal grids ⋮ Triggering cascades on undirected connected graphs ⋮ On reversible cascades in scale-free and Erdős-Rényi random graphs ⋮ Solving the feedback vertex set problem on undirected graphs ⋮ Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies ⋮ Two Hardness Results on Feedback Vertex Sets ⋮ MINIMUM FEEDBACK ARC SETS IN ROTATOR AND INCOMPLETE ROTATOR GRAPHS ⋮ Triggering cascades on strongly connected directed graphs ⋮ Feedback numbers of de Bruijn digraphs ⋮ An efficient algorithm for minimum feedback vertex sets in rotator graphs ⋮ Acyclic sum-list-colouring of grids and other classes of graphs ⋮ Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis ⋮ 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.

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

This page was built for publication: Almost exact minimum feedback vertex set in meshes and butterflies