6533b7d5fe1ef96bd1264fc8
RESEARCH PRODUCT
Searching for a strong double tracing in a graph
David Soler FernándezEnrique Benavent Lópezsubject
Statistics and ProbabilityDiscrete mathematicsInformation Systems and ManagementVoltage graphDirected graphManagement Science and Operations ResearchButterfly graphlaw.inventionCombinatoricslawGraph powerModeling and SimulationLine graphString graphDiscrete Mathematics and CombinatoricsNull graphGraph factorizationMathematicsofComputing_DISCRETEMATHEMATICSMathematicsdescription
Given a connected graph G, we present a polynomial algorithm which either finds a tour traversing each edge of G exactly two non-consecutive times, one in each direction, or decides that no such tour exists. The main idea of this algorithm is based on the modification of a proof given by Thomassen related to a problem proposed by Ore in 1951.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1998-06-01 | Top |