A note on line digraphs and the directed max-cut problem

DOI10.1016/0166-218X(90)90141-XzbMath0739.90070WikidataQ126654022 ScholiaQ126654022MaRDI QIDQ1174433

S. Singh

Publication date: 25 June 1992

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

undirected graphNP-complete problemdirected max-cut problemmaximum-weight stable set problemsupports of line digraphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (5)

Lower and upper bounds for the linear arrangement problem on interval graphs ⋮ On the complexity of recognizing directed path families ⋮ Functional graphs ⋮ A characterization problem on underlying graphs of line digraphs ⋮ Miscellaneous Digraph Classes

Cites Work

• On the number of common bases of two matroids
• Weakly bipartite graphs and the max-cut problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A note on line digraphs and the directed max-cut problem