Contractions, Removals and How to Certify 3-Connectivity in Linear Time

Details Contractions, Removals and How to Certify 3-Connectivity in Linear Time Contractions, Removals and How to Certify 3-Connectivity in Linear Time

2010-11-29

arxiv.org/abs/1011.6187v1

Computer Science

Data Structures and Algorithms

preliminary version

Scientific paper

It is well-known as an existence result that every 3-connected graph G=(V,E) on more than 4 vertices admits a sequence of contractions and a sequence of removal operations to K_4 such that every intermediate graph is 3-connected. We show that both sequences can be computed in optimal time, improving the previously best known running times of O(|V|^2) to O(|V|+|E|). This settles also the open question of finding a linear time 3-connectivity test that is certifying and extends to a certifying 3-edge-connectivity test in the same time. The certificates used are easy to verify in time O(|E|).

Affiliated with

Also associated with

No associations

Rating

Contractions, Removals and How to Certify 3-Connectivity in Linear Time 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 Contractions, Removals and How to Certify 3-Connectivity in Linear Time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Contractions, Removals and How to Certify 3-Connectivity in Linear Time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-220663