A note on line digraphs and the directed max-cut problem
From MaRDI portal
Publication:1174433
DOI10.1016/0166-218X(90)90141-XzbMath0739.90070MaRDI QIDQ1174433
Publication date: 25 June 1992
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
undirected graph; NP-complete problem; directed max-cut problem; maximum-weight stable set problem; supports of line digraphs
90C35: Programming involving graphs or networks
90C60: Abstract computational complexity for mathematical programming problems
05C85: Graph algorithms (graph-theoretic aspects)
05C20: Directed graphs (digraphs), tournaments
Cites Work