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 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)展开更多
IN this note all graphs are undirected, finite and simple. For a subgraph H of G,ε（H） andμ（H） denote the number of edges in H and the number of cycles in H respectively. H[X]denotes the subgraph of H induced by ...IN this note all graphs are undirected, finite and simple. For a subgraph H of G,ε（H） andμ（H） denote 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）, wewrite E<sub>G</sub>（X, Y）={xy∈E（G）|x∈X, y∈Y}. Sometimes E<sub>G</sub>（H, Y）=EG（V（H）,Y） is used for a subgraph H of G-Y. If T is a tree of G and e=uv∈G-E（T）with{u,v}V（T）, then T + e contains a unique cycle, denoted by C（T, e）.A tree-decomposition {T<sub>1</sub>, T<sub>2</sub>, …, T<sub>k</sub>} of a graph G is a partition of E （G）, say,E（G）=E<sub>1</sub> U E<sub>2</sub> U…U E<sub>k</sub>, such that for each i with 1≤i≤k, T<sub>i</sub>=G[E<sub>i</sub>] is a tree.展开更多
A tree decomposition of graph G=(V, E) is referred to as a partition of edge set E into edge-disjoint trees. Given (not necessarily distinct) vertices u-1, u-2...u-k∈V with k≥2, a sufficient and necessary condition ...A tree decomposition of graph G=(V, E) is referred to as a partition of edge set E into edge-disjoint trees. Given (not necessarily distinct) vertices u-1, u-2...u-k∈V with k≥2, a sufficient and necessary condition is given for a connected graph G=(V,E) to have a tree decomposition {T-1, T-2...T-k} such that V(T-i)=V{u-i}, i=1,2,... k.展开更多
一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G...一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度。一个合取范式(Conjunctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示。忽略公式因子图中边上的符号,得到一个二分图。文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。展开更多
For a graph G, if E(G) can be partitioned into several pairwise disjoint sets as{E1 , E2,...,El } such that the subgraph induced by Ei is a tree of order ki ) (i = 1, 2,... , l),then G is said to have a {k1, k2, ..., ...For a graph G, if E(G) can be partitioned into several pairwise disjoint sets as{E1 , E2,...,El } such that the subgraph induced by Ei is a tree of order ki ) (i = 1, 2,... , l),then G is said to have a {k1, k2, ..., kl }-tree-decomposition, denoted by { k1, k2 ,..., Kl } G.For k 1 and l 0, a collection (k,l) is the set of multigraphs such that G e Q(k,l)if and only if e(G) = k(G - 1) - l and (H) max{(k - 1)(H - 1),k(H -1) -l}for any subgraph H of G. We Prove that (1) If k 2,0 l 3 and G Q(k,l) oforder + 1, then {n,n,...,n -- l} E G. (2) If 2 and G (k,2) of ordern 3, then {n,n, ...,n,n-- 2} E G and {n,n,.. -1,n - 1} G. (3) If 3 andG g(k,3) of order n 4, then {n, n,... n,n-- 3} G ) {n,n,.., n,n-- 1,n -- 2} Gand {n,n,... n,n -- 1,n -- 1,n -- 1} 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.
文摘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)
文摘IN this note all graphs are undirected, finite and simple. For a subgraph H of G,ε（H） andμ（H） denote 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）, wewrite E<sub>G</sub>（X, Y）={xy∈E（G）|x∈X, y∈Y}. Sometimes E<sub>G</sub>（H, Y）=EG（V（H）,Y） is used for a subgraph H of G-Y. If T is a tree of G and e=uv∈G-E（T）with{u,v}V（T）, then T + e contains a unique cycle, denoted by C（T, e）.A tree-decomposition {T<sub>1</sub>, T<sub>2</sub>, …, T<sub>k</sub>} of a graph G is a partition of E （G）, say,E（G）=E<sub>1</sub> U E<sub>2</sub> U…U E<sub>k</sub>, such that for each i with 1≤i≤k, T<sub>i</sub>=G[E<sub>i</sub>] is a tree.
文摘A tree decomposition of graph G=(V, E) is referred to as a partition of edge set E into edge-disjoint trees. Given (not necessarily distinct) vertices u-1, u-2...u-k∈V with k≥2, a sufficient and necessary condition is given for a connected graph G=(V,E) to have a tree decomposition {T-1, T-2...T-k} such that V(T-i)=V{u-i}, i=1,2,... k.
文摘一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度。一个合取范式(Conjunctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示。忽略公式因子图中边上的符号,得到一个二分图。文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。
文摘For a graph G, if E(G) can be partitioned into several pairwise disjoint sets as{E1 , E2,...,El } such that the subgraph induced by Ei is a tree of order ki ) (i = 1, 2,... , l),then G is said to have a {k1, k2, ..., kl }-tree-decomposition, denoted by { k1, k2 ,..., Kl } G.For k 1 and l 0, a collection (k,l) is the set of multigraphs such that G e Q(k,l)if and only if e(G) = k(G - 1) - l and (H) max{(k - 1)(H - 1),k(H -1) -l}for any subgraph H of G. We Prove that (1) If k 2,0 l 3 and G Q(k,l) oforder + 1, then {n,n,...,n -- l} E G. (2) If 2 and G (k,2) of ordern 3, then {n,n, ...,n,n-- 2} E G and {n,n,.. -1,n - 1} G. (3) If 3 andG g(k,3) of order n 4, then {n, n,... n,n-- 3} G ) {n,n,.., n,n-- 1,n -- 2} Gand {n,n,... n,n -- 1,n -- 1,n -- 1} G.
