Computer Science – Data Structures and Algorithms
Scientific paper
2011-06-12
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.
Ilic Aleksandar
Ilic Andreja
No associations
LandOfFree
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.
Profile ID: LFWR-SCP-O-428828