The weighted feedback vertex set problem on distance-hereditary graphs
| Autor: | Chuan-Min Lee, 李權明 |
|---|---|
| Rok vydání: | 2000 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 88 A feedback vertex set F of a graph G=(V,E) is a subset of V such that the grpah induced by V\F has no cycles. If each vertex v of G is associated with a real number w(v), called the weight of vertex v, then G is a weighted graph.The weighted feedback vertex setp problem is to find a minimum weight feedback vertex set on a weighted grpah G. This problem is NP-hard on general graphs. A graph is Distance-hereditary if each pair of verteices has the same distance in every connected induced subgraph containing them. In this paper, we solve the veighted feedback vertex set problem on distance-hereditary grpahs in O(n+m) time by using dynamic programming technique. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|