New bounds on the size of the minimum feedback vertex set in meshes and butterflies.
From MaRDI portal
Publication:1853082
DOI10.1016/S0020-0190(02)00266-1zbMath1044.68934MaRDI QIDQ1853082
Panagiotis Kanellopoulos, Christos Kaklamanis, Ioannis Caragiannis
Publication date: 21 January 2003
Published in: Information Processing Letters (Search for Journal in Brave)
Related Items (13)
The size of graphs with given feedback vertex number ⋮ 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}$ ⋮ Feedback vertex sets on restricted bipartite graphs ⋮ Maximum induced forests in graphs of bounded treewidth ⋮ Dynamic monopolies and feedback vertex sets in hexagonal grids ⋮ Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies ⋮ Decycling bubble sort graphs ⋮ Two Hardness Results on Feedback Vertex Sets ⋮ MINIMUM FEEDBACK ARC SETS IN ROTATOR AND INCOMPLETE ROTATOR GRAPHS ⋮ An efficient algorithm for minimum feedback vertex sets in rotator graphs ⋮ Feedback vertex sets in star 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
- Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
- Feedback vertex sets and cyclically reducible graphs
- A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
This page was built for publication: New bounds on the size of the minimum feedback vertex set in meshes and butterflies.
