Name
Abstract | ||
|---|---|---|
Feedback vertex problems consist of removing a minimal number of vertices of a directed or undirected graph in order to make it acyclic. The problem is known to be NP -complete. In this paper we consider the variant on undirected graphs. The polyhedral structure of the feedback vertex set polytope is studied. We prove that this polytope is full dimensional and show that some inequalities are facet defining. We describe a new large class of valid constraints, the subset inequalities . A branch-and-cut algorithm for the exact solution of the problem is then outlined, and separation algorithms for the inequalities studied in the paper are proposed. A local search heuristic is described next. Finally, we create a library of 1400 randomly generated instances with the geometric structure suggested by the applications, and we computationally compare the two algorithmic approaches on our library. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1016/S0166-218X(99)00180-8 | Discrete Applied Mathematics |
Keywords | Field | DocType |
feedback vertex set,feedback vertex set problem,tabu search,undirected graph,branch-and-cut,local search heuristic,local search,exact solution,branch and cut | Graph theory,Discrete mathematics,Combinatorics,Vertex (geometry),Vertex (graph theory),Cycle graph,Directed acyclic graph,Vertex enumeration problem,Feedback arc set,Mathematics,Feedback vertex set | Journal |
Volume | Issue | ISSN |
101 | 1-3 | Discrete Applied Mathematics |
Citations | PageRank | References |
9 | 0.56 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lorenzo Brunetta | 1 | 98 | 8.94 |
| Francesco Maffioli | 2 | 271 | 44.39 |
| Marco Trubian | 3 | 594 | 51.20 |