Paperback Edition
Paperback
143 pages
$32.95
Choose vendor to order paperback edition
BrownWalker Press Amazon.com Barnes & Noble Return policy
PDF eBook
Sample Preview
Size 1278k
Free
Download a sample of the first 25 pages
Download Preview

Entire PDF eBook
2257k
$31
Get instant access to an entire eBook
Buy PDF Password Download Complete PDF
eBook editions

R² - Heaps with Suspended Relaxation for Manipulating Priority Queues and a New Algorithm for Reweighting Graphs

by Ruth Shrairman
small book icon  Paperback   small ebook icon   eBook PDF
Publisher:  Dissertation
Pub date:  2004
Pages:  143
ISBN-10:  1581122365
ISBN-13:  9781581122367
Categories:  Computer Science  Computers  Science

Abstract

This research is dedicated to two main problems in finding shortest paths in the graphs. The first problem is to find shortest paths from an origin to all other vertices in non-negatively weighted graph. The second problem is the same, except it is allowed that some edges are negative. This is a more difficult problem that can be solved by relatively complicated algorithms.

We attack the first problem by introducing a new data structure - Relaxed Heaps that implements efficiently two main operations critical for the improvement of Dijkstra's shortest path algorithm. R²heaps with suspended relaxation proposed in this research gives the best known worst-case time bounds of O(1) for a decrease_key operation and O(logn) for a delete_min operation. That results in the best worst-case running time for Dijkstra's algorithm O(m+nlogn), and represents an improvement over Fibonacci Heaps, which give the same , but amortized time bounds. The new data structure is simple and efficient in practical implementation. The empirical study with R²-heaps demonstrated strong advantage of its use for Dijkstra's algorithm over the "raw" Dijkstra's without heaps. This advantage is especially dramatic for sparse graphs. R²-heaps can be used in a large number of applications in which set manipulations should be implemented efficiently.

For the problem of finding shortest paths in graphs with some negative edges, we present a new approach of reweighting graphs by first reducing the graph to its canonical form, which allows to apply an effective algorithm to reweight the graph to one with non-negative edges only and simultaneously to find shortest paths from an origin to all other vertices in the graph. This approach allows to give new algebraic and geometric interpretations of the problem. The experiment with the Sweeping Algorithm demonstrated O(n² logn) expected time complexity.

These results open new prospects to improve algorithms for a wide variety of problems including different network optimization problems that use Dijkstra's algorithm as a subroutine, as well as multiple Operations Research and Modeling problems that can be reduced to finding shortest paths on graphs.



Paperback Edition
Paperback
143 pages
$32.95
Choose vendor to order paperback edition
BrownWalker Press Amazon.com Barnes & Noble Return policy
PDF eBook
Sample Preview
Size 1278k
Free
Download a sample of the first 25 pages
Download Preview

Entire PDF eBook
2257k
$31
Get instant access to an entire eBook
Buy PDF Password Download Complete PDF
eBook editions
Share this book



Relevant events
AUG
18
CRYPTO2024
44th Annual International Cryptology Conference 2024 The International Association for Cryptologic Research (IACR) is a non-profit scientific orga...
18 - 22 Aug 2024
Santa Barbara, United States
SEP
5
PEAI 2024
PEAI 2024 : The Economic Perspective on AI AI technology is progressing worldwide. The aim of the interdisciplinary conference is to ana...
05 - 06 Sep 2024
Johannesburg, South Africa
JUL
24
2024 the 10th International Conference on Virtual Reality (ICVR 2024) Publication: Accepted papers will be included in ICVR 2024 conference proceedings, which wil...
24 - 26 Jul 2024
Bournemouth, United Kingdom
JUL
24
BDE 2024
2024 6th International Conference on Big Data Engineering (BDE 2024) Accepted papers will be published in the ACM international conference proceedings (ISBN: 979-...
24 - 26 Jul 2024
Xining, China
JUL
25
2024 12th International Conference on Communications and Broadband Networking (ICCBN 2024) Publication: Accepted papers after proper registration and presentation will be collected in...
25 - 27 Jul 2024
Tibet, China
JUL
26
2024 6th Asia Conference on Machine Learning and Computing (ACMLC 2024) Conference Proceedings: Submissions will be reviewed by the conference technical committees,...
26 - 28 Jul 2024
Bangkok, Thailand
JUL
26
ICCNE 2024
2024 7th International Conference on Communications and Network Engineering (ICCNE 2024) Publication: Submitted papers will be peer reviewed by conference committees, and accepted p...
26 - 28 Jul 2024
Danang, Vietnam
JUL
26
ICCRI 2024
2024 the 7th International Conference on Control, Robotics and Informatics (ICCRI 2024) Publication: Submitted papers will be peer reviewed by conference committees, and accepted p...
26 - 28 Jul 2024
Danang, Vietnam
JUL
26
ICSCT 2024
2024 13th International Conference on Software and Computing Technologies (ICSCT 2024) Publications: International Journal of Computer Theory and Engineering (IJCTE, ISSN: 1793-82...
26 - 28 Jul 2024
Danang, Vietnam
JUL
26
AIBT 2024
2024 The 3rd International Conference on Artificial Intelligence and Blockchain Technology (AIBT 2024) Proceedings: Submitted papers will be Peer Reviewed (Double Blind) and the accepted ones wil...
26 - 28 Jul 2024
Beijing, China