New bounds on the size of the minimum feedback vertex set in meshes and butterflies.

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)

zbMATH Keywords

AlgorithmsInterconnection networksFeedback vertex set

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: New bounds on the size of the minimum feedback vertex set in meshes and butterflies.