Efficient Algorithm for Minimum Feedback Vertex Set Problem on Trapezoid Graphs
スポンサーリンク
概要
- 論文の詳細を見る
In an undirected graph, the feedback vertex set (FVS for short) problem is to find a set of vertices of minimum cardinality whose removal makes the graph acyclic. The FVS has applications to several areas such that combinatorial circuit design, synchronous systems, computer systems, VLSI circuits and so on. The FVS problem is known to be NP-hard on general graphs but interesting polynomial solutions have been found for some special classes of graphs. In this paper, we present an O(n2.68+γn) time algorithm for solving the FVS problem on trapezoid graphs, where γ is the total number of factors included in all maximal cliques.
- 2011-12-16
著者
-
Honma Hirotoshi
Department Of Information Engineering Kushiro National College Of Technology
-
KITAMURA Yutaro
Department of Intelligent Interaction Technologies, University of Tsukuba
-
Hirotoshi Honma
Department Of Information Engineering Kushiro National College Of Technology
-
Yutaro KITAMURA
Department of Intelligent Interaction Technologies, University of Tsukuba
-
Kitamura Yutaro
Department Of Intelligent Interaction Technologies University Of Tsukuba
-
Yutaro Kitamura
Department Of Intelligent Interaction Technologies University Of Tsukuba
関連論文
- An Optimal Parallel Algorithm for Constructing a Spanning Forest on Trapezoid Graphs
- An Optimal Parallel Algorithm for Finding All Hinge Vertices of a Circular-Arc Graph
- A Parallel Algorithm for Finding All Hinge Vertices of an Interval Graph
- An Optimal Parallel Algorithm for Constructing a Spanning Tree on Circular Permutation Graphs
- Efficient Algorithm for Minimum Feedback Vertex Set Problem on Trapezoid Graphs
- An Algorithm for Minimum Feedback Vertex Set Problem on a Trapezoid Graph
- Linear Time Algorithms for Finding Articulation and Hinge Vertices of Circular Permutation Graphs
- A Linear-Time Algorithm for Constructing a Spanning Tree on Circular Trapezoid Graphs