کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430927 | 688233 | 2012 | 7 صفحه PDF | دانلود رایگان |
2-Joins are edge cutsets that naturally appear in the decomposition of several classes of graphs closed under taking induced subgraphs, such as balanced bipartite graphs, even-hole-free graphs, perfect graphs and claw-free graphs. Their detection is needed in several algorithms, and is the slowest step for some of them. The classical method to detect a 2-join takes O(n3m)O(n3m) time where n is the number of vertices of the input graph and m is the number of its edges. To detect non-path 2-joins (special kinds of 2-joins that are needed in all of the known algorithms that use 2-joins), the fastest known method takes time O(n4m)O(n4m). Here, we give an O(n2m)O(n2m)-time algorithm for both of these problems. A consequence is a speed-up of several known algorithms.
Journal: Journal of Discrete Algorithms - Volume 17, December 2012, Pages 60–66