Detecting 2-joins faster

Details Detecting 2-joins faster Detecting 2-joins faster

2011-07-20

arxiv.org/abs/1107.3977v1

Computer Science

Data Structures and Algorithms

Scientific paper

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(n^3m) time where n is the number of vertices of the input graph and m 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(n^4m). Here, we give an O(n^2m)-time algorithm for both of these problems. A consequence is a speed up of several known algorithms.

Affiliated with

Also associated with

No associations

Rating

Detecting 2-joins faster does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Detecting 2-joins faster, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detecting 2-joins faster will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-35588