Statements (28)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
gptkb:mathematical_concept
|
| gptkbp:alsoKnownAs |
Route inspection problem
|
| gptkbp:appliesTo |
directed graphs
undirected graphs mixed graphs |
| gptkbp:category |
mathematical optimization
graph traversal |
| gptkbp:complexity |
NP-hard (for mixed graphs)
polynomial time (for undirected and directed graphs) |
| gptkbp:describes |
finding a shortest closed path or circuit that visits every edge of a graph
|
| gptkbp:field |
combinatorial optimization
graph theory |
| gptkbp:firstPublished |
1962
|
| gptkbp:generalizes |
Eulerian path problem
|
| https://www.w3.org/2000/01/rdf-schema#label |
Chinese postman problem
|
| gptkbp:namedAfter |
Meigu Guan
|
| gptkbp:relatedTo |
gptkb:traveling_salesman_problem
gptkb:Eulerian_circuit |
| gptkbp:solutionExistsIf |
all vertices have even degree (for undirected graphs)
|
| gptkbp:solvedBy |
adding duplicate edges to make all degrees even
matching odd degree vertices |
| gptkbp:supportsAlgorithm |
Blossom algorithm
Edmonds' matching algorithm |
| gptkbp:usedIn |
postal delivery
street sweeping garbage collection routing |
| gptkbp:bfsParent |
gptkb:traveling_salesman_problem
|
| gptkbp:bfsLayer |
6
|