On negative cycles in mixed graphs (Q1071027)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On negative cycles in mixed graphs |
scientific article; zbMATH DE number 3937202
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On negative cycles in mixed graphs |
scientific article; zbMATH DE number 3937202 |
Statements
On negative cycles in mixed graphs (English)
0 references
1985
0 references
It is shown that for mixed graphs, i.e., graphs having both directed and undirected edges, with a length function defined on the edges, the problems of detecting negative cycles and of finding the shortest path in the absence of negative cycles are NP-complete.
0 references
algorithm
0 references
mixed graphs
0 references
negative cycles
0 references
shortest path
0 references
NP-complete
0 references
0.9306832
0 references
0.8943542
0 references
0.8943542
0 references
0.88690054
0 references
0.88690054
0 references
0.88169837
0 references
0.8801036
0 references
