- 【Updated on May 12, 2025】 Integration of CiNii Dissertations and CiNii Books into CiNii Research
- Trial version of CiNii Research Automatic Translation feature is available on CiNii Labs
- Suspension and deletion of data provided by Nikkei BP
- Regarding the recording of “Research Data” and “Evidence Data”
Cut cover problem in directed graphs
Description
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.
Journal
-
- 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
