Title :
Cut cover problem in directed graphs
Author :
Watanabe, Kaoru ; Sengoku, Masakazu ; Tamura, Hiroshi ; Shinoda, Shoji
Author_Institution :
Osaka Electro-Commun. Univ., Japan
Abstract :
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
Keywords :
computational complexity; directed graphs; graph colouring; NP-complete problem; arc set; cut cover problem; digraph; directed cuts; directed graphs; minimum cut cover; vertex set; Communication networks; Frequency; Labeling; Spread spectrum communication; Sufficient conditions;
Conference_Titel :
Circuits and Systems, 1998. IEEE APCCAS 1998. The 1998 IEEE Asia-Pacific Conference on
Conference_Location :
Chiangmai
Print_ISBN :
0-7803-5146-0
DOI :
10.1109/APCCAS.1998.743918
