DocumentCode
2536486
Title
Cut cover problem in directed graphs
Author
Watanabe, Kaoru ; Sengoku, Masakazu ; Tamura, Hiroshi ; Shinoda, Shoji
Author_Institution
Osaka Electro-Commun. Univ., Japan
fYear
1998
fDate
24-27 Nov 1998
Firstpage
703
Lastpage
706
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;
fLanguage
English
Publisher
ieee
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
Type
conf
DOI
10.1109/APCCAS.1998.743918
Filename
743918
Link To Document