|
|||||
|
|
A POLYNOMIAL ALGORITHM FOR FINDING THE MINIMUM FEEDBACK VERTEX SET OF A 3-REGULAR SIMPLE GRAPH 1 |
|
| Institution: | 1. School of Computer Science and Engineering, Central South University, Changsha, China;2. Department of Computing, Hong Kong Polytechnic University, Hong Kong, China;1. Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA 15213, USA;2. Krannert School of Management, Purdue University, West Lafayette, IN 47906, USA |
| Abstract: | A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vertex set of a 3-regular simple graph is provided. |
| Keywords: | maximum genus nonseparating independent number feedback vertex set 3-regular graph adjacency matching 05C45 |
| 本文献已被 ScienceDirect 等数据库收录！ | |