IN this note all graphs are undirected, finite and simple. For a subgraph H of G, V(H), E(H), ε(H) and μ(H) denote the set of vertices, the set of edges, the number of edges in H and the number of cycles in H respec...IN this note all graphs are undirected, finite and simple. For a subgraph H of G, V(H), E(H), ε(H) and μ(H) denote the set of vertices, the set of edges, the number of edges in H and the number of cycles in H respectively. H[X] denotes the subgraph of H induced by X. Given two disjoint subsets X and Y of V(G), we write E_G(X, Y)={xy∈E(G)展开更多
Many difficult (often NP-complete) optimization problems can be solved efficiently on graphs of small tree-width with a given tree-decomposition.In this paper,it is discussed how to solve the minimum feedback vertex s...Many difficult (often NP-complete) optimization problems can be solved efficiently on graphs of small tree-width with a given tree-decomposition.In this paper,it is discussed how to solve the minimum feedback vertex set problem and the minimum vertex feedback edge set problem efficiently by using dynamic programming on a tree-decomposition.展开更多
文摘IN this note all graphs are undirected, finite and simple. For a subgraph H of G, V(H), E(H), ε(H) and μ(H) denote the set of vertices, the set of edges, the number of edges in H and the number of cycles in H respectively. H[X] denotes the subgraph of H induced by X. Given two disjoint subsets X and Y of V(G), we write E_G(X, Y)={xy∈E(G)
基金Partially supported by the National Natural Science Foundation of China( 1 0 2 71 0 65
文摘Many difficult (often NP-complete) optimization problems can be solved efficiently on graphs of small tree-width with a given tree-decomposition.In this paper,it is discussed how to solve the minimum feedback vertex set problem and the minimum vertex feedback edge set problem efficiently by using dynamic programming on a tree-decomposition.
