Title: A note on line digraphs and the directed max-cut problem
Abstract: The support of a digraph is the undirected graph arising when directions of edges are ignored. We prove that recognizing supports of line digraphs of digraphs is an NP-Complete problem. Then we observe that solvable cases of the directed max-cut problem arise from solvable cases of the maximum-weight stable set problem via supports of line digraphs; in particular, we investigate digraphs G such that the support of the line digraph of G is perfect.
Publication Year: 1990
Publication Date: 1990-12-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 14
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot