A note on line digraphs and the directed max-cut problem (Q1174433): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q328466 |
Changed an Item |
||
| Property / reviewed by | |||
| Property / reviewed by: Louis Caccetta / rank | |||
Normal rank | |||
Revision as of 00:24, 13 February 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on line digraphs and the directed max-cut problem |
scientific article |
Statements
A note on line digraphs and the directed max-cut problem (English)
0 references
25 June 1992
0 references
The support of a simple digraph is the undirected graph arising when directions of edges are ignored. The authors prove that recognizing supports of line digraphs is an NP-complete problem. Further, they 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, they investigate digraphs \(G\) such that the support of the line digraph \(G\) is perfect.
0 references
undirected graph
0 references
supports of line digraphs
0 references
NP-complete problem
0 references
directed max-cut problem
0 references
maximum-weight stable set problem
0 references
