Compact minimum-weight perfect matching in cubic arithmetic time
ProvedVehicleRoutingSurvey.Routing.compact_matching_cubic_existsgraph-theoryrural-postman
There is a fixed arithmetic-RAM block for the compact minimum-weight perfect matching problem used by the rural postman algorithm. The block implements the representation and execution contract CompactMateBlockSpec with constant 27648.
Preamble
import Definitions.Def_VehicleRoutingSurvey_RuralPostman1979_Part02 open VehicleRoutingSurvey.Routing
Formal statement
theorem VehicleRoutingSurvey.Routing.compact_matching_cubic_exists : ∃ matching : List ArithmeticInstruction, CompactMateBlockSpec matching 27648 := by sorry
Source
J. K. Lenstra and A. H. G. Rinnooy Kan, Complexity of vehicle routing and scheduling problems (1979), Table 3, printed p. 5. https://ir.cwi.nl/pub/9658/9658D.pdf