Feedback vertex sets in star graphs

DOI10.1016/j.ipl.2003.11.001zbMath1176.05081OpenAlexW1995044685MaRDI QIDQ1029080

Jou-Ming Chang, Fu-Hsing Wang, Yue-Li Wang

Publication date: 9 July 2009

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2003.11.001

zbMATH Keywords

algorithmsanalysis of algorithmsinterconnection networksstar graphsfeedback vertex sets

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

Circular convex bipartite graphs: feedback vertex sets ⋮ New upper bounds on feedback vertex numbers in butterflies ⋮ The decycling number of $P_{m} \square P_{n}^{\ast}$ ⋮ Decycling bipartite graphs ⋮ Feedback vertex sets on restricted bipartite graphs ⋮ New bounds on the decycling number of generalized de Bruijn digraphs ⋮ On the bounds of feedback numbers of \((n,k)\)-star graphs ⋮ On the decycling number of generalized Kautz digraphs ⋮ The decycling number of generalized Petersen graphs ⋮ 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 ⋮ Circular Convex Bipartite Graphs: Feedback Vertex Set

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
• New bounds on the size of the 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 group-theoretic model for symmetric interconnection networks
• A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem

This page was built for publication: Feedback vertex sets in star graphs