Reverse Line Graph Construction: The Matrix Relabeling Algorithm MARINLINGA Versus Roussopoulos's Algorithm

Details Reverse Line Graph Construction: The Matrix Relabeling Algorithm MARINLINGA Versus Roussopoulos's Algorithm Reverse Line Graph Construction: The Matrix Relabeling Algorithm MARINLINGA Versus Roussopoulos's Algorithm

2010-05-06

arxiv.org/abs/1005.0943v3

Mathematics

Combinatorics

30 pages, 24 figures

Scientific paper

We propose a new algorithm MARINLINGA for reverse line graph computation, i.e., constructing the original graph from a given line graph. Based on the completely new and simpler principle of link relabeling and endnode recognition, MARINLINGA does not rely on Whitney's theorem while all previous algorithms do. MARINLINGA has a worst case complexity of O(N^2), where N denotes the number of nodes of the line graph. We demonstrate that MARINLINGA is more time-efficient compared to Roussopoulos's algorithm, which is well-known for its efficiency.

Affiliated with

Also associated with

No associations

Rating

Reverse Line Graph Construction: The Matrix Relabeling Algorithm MARINLINGA Versus Roussopoulos's Algorithm 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 Reverse Line Graph Construction: The Matrix Relabeling Algorithm MARINLINGA Versus Roussopoulos's Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reverse Line Graph Construction: The Matrix Relabeling Algorithm MARINLINGA Versus Roussopoulos's Algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-25993