کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414320 | 680888 | 2012 | 10 صفحه PDF | دانلود رایگان |
Let G be an unweighted graph of complexity n embedded in a surface of genus g, orientable or not. We describe improved algorithms to compute a shortest non-contractible and a shortest non-separating cycle in G.If k is an integer, we can compute such a non-trivial cycle with length at most k in O(gnk)O(gnk) time, or correctly report that no such cycle exists. In particular, on a fixed surface, we can test in linear time whether the edge-width or face-width of a graph is bounded from above by a constant. This also implies an output-sensitive algorithm to compute a shortest non-trivial cycle that runs in O(gnk0)O(gnk0) time, where k0k0 is the length of the cycle.We also give an approximation algorithm for the shortest non-trivial cycle. If a parameter 0<ε<10<ε<1 is given, we compute in O(gn/ε)O(gn/ε) time a non-trivial cycle whose length is at most 1+ε1+ε times the length of the shortest non-trivial cycle.
Journal: Computational Geometry - Volume 45, Issues 5–6, July 2012, Pages 215–224