| dbo:abstract
|
- In computer science and graph theory, the zero-weight cycle problem is the problem of deciding whether a directed graph with weights on the edges (which may be positive or negative or zero) has a cycle in which the sum of weights is 0. A related problem is to decide whether the graph has a cycle in which the sum of weights is less than 0. This related problem can be solved in polynomial time using the Bellman–Ford algorithm. In contrast, detecting a cycle of weight exactly 0 is an NP-complete problem. The problem is in NP since, given a cycle, it is easy to verify that its weight is 0. The proof of NP-hardness is by reduction from the subset sum problem. In this problem we are given a set of numbers, positive and some negative, and have to decide whether there exists a subset whose sum is exactly 0. Given an instance of subset-sum with n numbers, construct an instance of zero-weight-cycle as follows. Construct a graph with 2n vertices. For each number ai the graph contains two vertices: ui and vi. From each ui, there is only one outgoing edge, which goes to vi and has weight ai. From each vi, there are n outgoing edges, which go to each uj and have weights 0. Any cycle in this graph have the form u1-v1-u2-v2-...-uk-vk. The weight of a cycle is 0, iff the sum of all weights between each ui and its corresponding vi is 0, iff the sum of all corresponding ai is 0, iff there is a subset with a sum of 0. (en)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 2504 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- In computer science and graph theory, the zero-weight cycle problem is the problem of deciding whether a directed graph with weights on the edges (which may be positive or negative or zero) has a cycle in which the sum of weights is 0. A related problem is to decide whether the graph has a cycle in which the sum of weights is less than 0. This related problem can be solved in polynomial time using the Bellman–Ford algorithm. In contrast, detecting a cycle of weight exactly 0 is an NP-complete problem. The problem is in NP since, given a cycle, it is easy to verify that its weight is 0. (en)
|
| rdfs:label
|
- Zero-weight cycle problem (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is foaf:primaryTopic
of | |
