Efficient algorithm for the vertex connectivity of trapezoid graphs

Details Efficient algorithm for the vertex connectivity of trapezoid graphs Efficient algorithm for the vertex connectivity of trapezoid graphs

2011-06-15

arxiv.org/abs/1106.3037v1

Computer Science

Data Structures and Algorithms

12 pages, 2 figures

Scientific paper

The intersection graph of a collection of trapezoids with corner points lying on two parallel lines is called a trapezoid graph. These graphs and their generalizations were applied in various fields, including modeling channel routing problems in VLSI design and identifying the optimal chain of non-overlapping fragments in bioinformatics. Using modified binary indexed tree data structure, we design an algorithm for calculating the vertex connectivity of trapezoid graph $G$ with time complexity $O (n \log n)$, where $n$ is the number of trapezoids. Furthermore, we establish sufficient and necessary condition for a trapezoid graph $G$ to be bipartite and characterize trees that can be represented as trapezoid graphs.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-659583