کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421087 | 684132 | 2015 | 10 صفحه PDF | دانلود رایگان |
Using graph products we present an O(|V|2|E|+|V|3log|V|)O(|V|2|E|+|V|3log|V|) separation algorithm for the nonsimple 11-wheel inequalities by Cheng and Cunningham (1997) of the stable set polytope, which is faster than their O(|V|4)O(|V|4) algorithm.There are two ingredients for our algorithm. The main improvement stems from a reduction of the separation problem to multiple shortest path problems in an auxiliary graph having only 6|V|6|V| vertices and 9|E|9|E| arcs, thereby preserving low sparsity. Then Johnson’s algorithm can be applied to the auxiliary graph of same sparsity as the original one.In contrast, Cheng and Cunningham’s auxiliary graph is by construction dense, |E|=O(|V|2)|E|=O(|V|2), so application of Johnson’s algorithm provides no large improvement.
Journal: Discrete Applied Mathematics - Volume 195, 20 November 2015, Pages 74–83