返回Google圖書搜尋

Complexity of Circuit Intersection in Graphs

出版	Weizmann Institute of Science, Department of Applied Mathematics and Computer Science, 1992
URL	http://books.google.com.hk/books?id=uBLbGwAACAAJ&hl=&source=gbs_api

註釋Abstract: "Consider the decision problem Strict Bounded Circuit Intersection (SBCI): Given a finite graph G = (V, E) and K [element] Z[superscript +]. Is there a subset E' [subset] E with [abs E'] [> or =] K such that [abs (E' [intersection] C)] [abs C]/L for every circuit C of G? The problem Nonstrict BCI (NBCI) is the same, except that [abs (E' [intersection] C)] [abs C]/L is replaced by [abs (E' [intersection] C)] [or =] [abs C]/L. It is proved that SBCI is NP-complete for every fixed L [ or =] 2 even if G is planar and bipartite, and NBCI is NP-complete for every fixed L [ or =] 3 even if G is a planar. For every fixed L [ or =] 4 it is NP-complete even if G is planar and bipartite.