Cut cover problem in directed graphs
説明
Let D=(V, A) be the digraph with a vertex set V and an arc set A. A cut cover in D is a family of (directed) cuts such that each are of A belongs to some cut of this family. A minimum cut cover in U is one of minimum size. We say the problem of finding a minimum cut cover of a given digraph to be the minimum cut cover problem for digraphs. In this paper we consider the problem for digraphs, and show that this problem is NP-complete.
収録刊行物
-
- IEEE. APCCAS 1998. 1998 IEEE Asia-Pacific Conference on Circuits and Systems. Microelectronics and Integrating Systems. Proceedings (Cat. No.98EX242)
-
IEEE. APCCAS 1998. 1998 IEEE Asia-Pacific Conference on Circuits and Systems. Microelectronics and Integrating Systems. Proceedings (Cat. No.98EX242) 703-706, 2002-11-27
IEEE
