On vertex covers and matching number of trapezoid graphs

Details On vertex covers and matching number of trapezoid graphs On vertex covers and matching number of trapezoid graphs

2011-06-12

arxiv.org/abs/1106.2351v1

Computer Science

Data Structures and Algorithms

9 pages, 1 figure, 4 algorithms

Scientific paper

The intersection graph of a collection of trapezoids with corner points lying on two parallel lines is called a trapezoid graph. Using binary indexed tree data structure, we improve algorithms for calculating the size and the number of minimum vertex covers (or independent sets), as well as the total number of vertex covers, and reduce the time complexity from $O (n^2)$ to $O (n \log n)$, where $n$ is the number of trapezoids. Furthermore, we present the family of counterexamples for recently proposed algorithm with time complexity $O (n^2)$ for calculating the maximum cardinality matching in trapezoid graphs.

Affiliated with

Also associated with

No associations

Rating

On vertex covers and matching number of trapezoid graphs 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 On vertex covers and matching number of trapezoid graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On vertex covers and matching number of trapezoid graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-428828