Name
Abstract | ||
|---|---|---|
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 0(n(2.68) + gamma n) time algorithm for solving the FVS problem on trapezoid graphs, where gamma is the total number of factors included in all maximal cliques. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1587/transfun.E94.A.1381 | IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES |
Keywords | Field | DocType |
design and analysis of algorithms, feedback vertex set, trapezoid graphs, NP-hard | Discrete mathematics,Combinatorics,Vertex (graph theory),Cycle graph,Algorithm,Vertex cover,Pathwidth,Mathematics,Feedback arc set,Feedback vertex set,Trapezoid graph,Maximal independent set | Journal |
Volume | Issue | ISSN |
E94A | 6 | 0916-8508 |
Citations | PageRank | References |
0 | 0.34 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hirotoshi Honma | 1 | 30 | 9.77 |
| Yutaro Kitamura | 2 | 0 | 0.34 |
| Shigeru Masuyama | 3 | 107 | 28.06 |