Paperback Edition
Paperback
143 pages
$32.95
Choose vendor to order paperback edition
BrownWalker Press
Amazon.com
Barnes & Noble
Harvard Book Store
Return policy
PDF eBook
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


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
Harvard Book Store
Return policy
PDF eBook
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
DEC
11
IKBS 2025
2025 International Conference of Intelligent and Knowledge-Based Systems (IKBS 2025)
2025 International Conference on Intelligent and Knowledge-Based Systems (IKBS 2025) is organized by Nanchang Hangkong University and will be held in Nanchang, China during December 11-14, 2025.
The IKBS is a flagship a...
2025 International Conference of Intelligent and Knowledge-Based Systems (IKBS 2025)
2025 International Conference on Intelligent and Knowledge-Based Systems (IKBS 2025) is organized by Nanchang Hangkong University and will be held ...
2025 International Conference of Intelligent and Knowledge-Based Systems (IKBS 2025)
2025 International Conference on Intelligent and Knowledge-Based Systems ...
2025 International Conference of Intelligent and Knowledge-Based Systems (IKBS 2025)
2025 International Conference on Intelligent and...
11 - 14 Dec 2025
Nanchang, China
DEC
15
AGU25
American Geophysical Union (AGU) Fall Meeting
The submission period for session, town hall and workshop proposals for AGU25 will open March 2025.
Description: The largest Earth and space science meeting in the world, attracting scientists from around the globe.
...
American Geophysical Union (AGU) Fall Meeting
The submission period for session, town hall and workshop proposals for AGU25 will open March 2025.
Description: The largest Earth and space sci...
American Geophysical Union (AGU) Fall Meeting
The submission period for session, town hall and workshop proposals for A...
American Geophysical Union (AGU) Fall Meeting
The submission period for session, town hall and...
15 - 19 Dec 2025
New Orleans, United States
OCT
23
WCSP 2025
The Seventeenth International Conference on Wireless Communications and Signal Processing (WCSP 2025)
WCSP is an annual International Conference on Wireless Communications and Signal Processing (WCSP). The aim of the conference is to provide an international forum that brings together researchers from academia and practiti...
The Seventeenth International Conference on Wireless Communications and Signal Processing (WCSP 2025)
WCSP is an annual International Conference on Wireless Communications and Signal Processing (WCSP). The aim of the conference is to provide an inte...
The Seventeenth International Conference on Wireless Communications and Signal Processing (WCSP 2025)
WCSP is an annual International Conference on Wireless Communications and...
The Seventeenth International Conference on Wireless Communications and Signal Processing (WCSP 2025)
WCSP is an annual International Conference on Wi...
23 - 25 Oct 2025
Chongqing, China
OCT
24
ICBDT 2025
2025 8th International Conference on Big Data Technologies (ICBDT 2025)
Publication:
Submitted papers will be peer reviewed by conference committees, and accepted papers will be included in ICBDT 2025 conference proceedings.
2025 8th International Conference on Big Data Technologies (ICBDT 2025)
Publication:
Submitted papers will be peer reviewed by conference committees, and accepted papers will be included in ICBDT 2025 conference procee...
2025 8th International Conference on Big Data Technologies (ICBDT 2025)
Publication:
Submitted papers will be peer reviewed by conference commit...
2025 8th International Conference on Big Data Technologies (ICBDT 2025)
Publication:
Submitted papers will be peer revi...
24 - 26 Oct 2025
Nanchang, China
OCT
24
ICARSH
10th International Conference on Advanced Research in Social Sciences and Humanities
10th International Conference on Advanced Research in Social Sciences and Humanities 2025
Dates: 24 – 26 October 2025
Location: Geneva, Switzerland
Venue: The Domaine Barton, Geneva Graduate Institute, Villa Barton
...
10th International Conference on Advanced Research in Social Sciences and Humanities
10th International Conference on Advanced Research in Social Sciences and Humanities 2025
Dates: 24 – 26 October 2025
Location: Geneva, Switzerla...
10th International Conference on Advanced Research in Social Sciences and Humanities
10th International Conference on Advanced Research in Social Sciences and...
10th International Conference on Advanced Research in Social Sciences and Humanities
10th International Conference on Advanced Resear...
24 - 26 Oct 2025
Geneva, Switzerland
OCT
24
ICRCV 2025
2025 7th International Conference on Robotics and Computer Vision (ICRCV 2025)
Paper Publication:
Accepted full papers will be published in ICRCV 2025 Conference Proceedings and submitted for Ei Compendex, Scopus.
ICRCV 2021-2024 conference proceedings has been archived in IEEE Xplore and indexed b...
2025 7th International Conference on Robotics and Computer Vision (ICRCV 2025)
Paper Publication:
Accepted full papers will be published in ICRCV 2025 Conference Proceedings and submitted for Ei Compendex, Scopus.
ICRCV 2021...
2025 7th International Conference on Robotics and Computer Vision (ICRCV 2025)
Paper Publication:
Accepted full papers will be published in ICRCV 2025 ...
2025 7th International Conference on Robotics and Computer Vision (ICRCV 2025)
Paper Publication:
Accepted full papers will be...
24 - 26 Oct 2025
Hong Kong, China
OCT
24
ICSPS 2025
2025 The 17th International Conference on Signal Processing Systems (ICSPS 2025)
Publication:
Submitted papers will be peer reviewed by program committees and technical committee, and accepted papers will be published into conference proceedings by IEEE after registration and presentation. The procee...
2025 The 17th International Conference on Signal Processing Systems (ICSPS 2025)
Publication:
Submitted papers will be peer reviewed by program committees and technical committee, and accepted papers will be published into con...
2025 The 17th International Conference on Signal Processing Systems (ICSPS 2025)
Publication:
Submitted papers will be peer reviewed by program committe...
2025 The 17th International Conference on Signal Processing Systems (ICSPS 2025)
Publication:
Submitted papers will be peer rev...
24 - 26 Oct 2025
Chengdu, China
OCT
24
ICCPR 2025
2025 14th International Conference on Computing and Pattern Recognition (ICCPR 2025)
Publication&Indexing:
1. International Conference Proceedings: Communications in Computer and Information Science (CCIS) – Springer, indexed by Scopus, EI-Compendex, etc.
2. Journal of Advances in Information Technology...
2025 14th International Conference on Computing and Pattern Recognition (ICCPR 2025)
Publication&Indexing:
1. International Conference Proceedings: Communications in Computer and Information Science (CCIS) – Springer, indexed by S...
2025 14th International Conference on Computing and Pattern Recognition (ICCPR 2025)
Publication&Indexing:
1. International Conference Proceedings: Communica...
2025 14th International Conference on Computing and Pattern Recognition (ICCPR 2025)
Publication&Indexing:
1. International Conferen...
24 - 26 Oct 2025
Beijing, China
OCT
24
RCAE 2025
2025 8th International Conference on Robotics, Control and Automation Engineering (RCAE 2025)
Publication:
Submitted papers will be peer reviewed by conference committees. Accepted full papers will be published in RCAE 2025 Conference Proceedings, which will be published in IEEE Xplore, and indexed by EI Compendex...
2025 8th International Conference on Robotics, Control and Automation Engineering (RCAE 2025)
Publication:
Submitted papers will be peer reviewed by conference committees. Accepted full papers will be published in RCAE 2025 Conference Proce...
2025 8th International Conference on Robotics, Control and Automation Engineering (RCAE 2025)
Publication:
Submitted papers will be peer reviewed by conference commit...
2025 8th International Conference on Robotics, Control and Automation Engineering (RCAE 2025)
Publication:
Submitted papers will be peer revi...
24 - 26 Oct 2025
Xi'an, China
OCT
24
IMMS 2025
2025 the 8th International Conference on Information Management and Management Science (IMMS 2025)
Publication:
After a careful reviewing process, all accepted papers after proper registration and presentation, will be published into Conference Publishing Services (CPS), and submitted to IEEE Xplore for indexing by Ei...
2025 the 8th International Conference on Information Management and Management Science (IMMS 2025)
Publication:
After a careful reviewing process, all accepted papers after proper registration and presentation, will be published into Conference...
2025 the 8th International Conference on Information Management and Management Science (IMMS 2025)
Publication:
After a careful reviewing process, all accepted papers aft...
2025 the 8th International Conference on Information Management and Management Science (IMMS 2025)
Publication:
After a careful reviewing process...
24 - 26 Oct 2025
Beijing, China