A note on line digraphs and the directed max-cut problem (Q1174433)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 8714
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A note on line digraphs and the directed max-cut problem |
scientific article; zbMATH DE number 8714 |
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
0.90589696
0 references
0.9042127
0 references
0 references
0 references
0.8825439
0 references
0.8809943
0 references
0.8808631
0 references
0.87877005
0 references
0.8774601
0 references
0.87426704
0 references
