search

QuEraComputing / UnitDiskMapping.jl

Reduce several arbitrary-connectivity optimization problems into maximum independent set problems on a grid
https://github.com/QuEraComputing/UnitDiskMapping.jl
Other
16 stars 3 forks source link

Fix the path decomposition #26

Closed GiggleLiu closed 2 years ago

GiggleLiu commented 2 years ago

@minhthin1028 I notice that the ordering of vertex seperation is different from the vertex ordering of path decomposition. They are reversible to each other. Please check the mapping you have done to make sure they are correct.

minhthin1028 commented 2 years ago

Thanks for noticing and fixing it! @GiggleLiu But also, having the vertex separation order (if it is the correct order reversed) should not change the mapping of the graph, right?

GiggleLiu commented 2 years ago

Thanks for noticing and fixing it! @GiggleLiu But also, having the vertex separation order (if it is the correct order reversed) should not change the mapping of the graph, right?

It can change the mapping of the graph. For example, the new mapped Petersen graph has one less vertex. Sometimes, the depth can increase when using reversed ordering.