Almost exact minimum feedback vertex set in meshes and butterflies

DOI10.1016/S0020-0190(98)00039-8MaRDI QIDQ1129019zbMATH OpenOpenAlexFDO

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

Cites work

• scientific article; zbMATH DE number 3858396 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A linear-time algorithm for the weighted feedback vertex problem on interval graphs
• Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
• On locating minimum feedback vertex sets
• On the feedback vertex set problem in permutation graphs
• Size bounds for dynamic monopolies

Cited in

(28)

• Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis
• Triggering cascades on undirected connected graphs
• An efficient algorithm for minimum feedback vertex sets in rotator graphs
• Minimum feedback vertex sets in shuffle-based interconnection networks
• Acyclic sum-list-colouring of grids and other classes of graphs
• The decycling number of \(P_m\square P^\ast_n\)
• New upper bounds on feedback vertex numbers in butterflies
• On reversible cascades in scale-free and Erdős-Rényi random graphs
• Feedback vertex set in hypercubes
• A feedback vertex set of 2-degenerate graphs
• Solving the feedback vertex set problem on undirected graphs
• New bounds on the size of the minimum feedback vertex set in meshes and butterflies.
• Feedback vertex sets on restricted bipartite graphs
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies
• Feedback vertex sets in star graphs
• Minimum feedback arc sets in rotator and incomplete rotator graphs
• Feedback vertex sets in mesh-based networks
• The integrity of a cubic graph
• Minimum feedback vertex set and acyclic coloring.
• The size of graphs with given feedback vertex number
• Decycling bipartite graphs
• Feedback numbers of Kautz digraphs
• Dynamic monopolies and feedback vertex sets in hexagonal grids
• Feedback numbers of de Bruijn digraphs
• Triggering cascades on strongly connected directed graphs
• Target set selection on generalized pancake graphs
• Two Hardness Results on Feedback Vertex Sets

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

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