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
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 Harvard Book Store 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
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 ...
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
13
IJDMS
International Journal of Database Management Systems (IJDMS) International Journal of Database Management Systems (IJDMS) IJDMS is indexed World Journal Clout Index (WJCI) ISSN : 0975-5705 (Online); 0975-5985 (Print) http://airccse.org/journal/ijdms/index.html Scope & ...
International Journal of Database Management Systems (IJDMS) International Journal of Database Management Systems (IJDMS) IJDMS is indexed World Journal Clout Index (WJCI) ISSN : 0975-5705 (Online); 0...
International Journal of Database Management Systems (IJDMS) International Journal of Database Management Systems (IJDMS) IJDMS i...
International Journal of Database Management Systems (IJDMS) International Journal of Database Management S...
13 - 20 Oct 2025
Online Event | India
OCT
16
IEEE ICCT 2025
2025 IEEE 25th International Conference on Communication Technology (25th IEEE ICCT) Proceedings Publication: Accepted academic papers will be published by IEEE, and conference papers that meet IEEE Standards can be indexed by the IEEE Xplore Digital Library. IEEE ICCT2025 has been listed on IEEE confere...
2025 IEEE 25th International Conference on Communication Technology (25th IEEE ICCT) Proceedings Publication: Accepted academic papers will be published by IEEE, and conference papers that meet IEEE Standards can be indexed by the ...
2025 IEEE 25th International Conference on Communication Technology (25th IEEE ICCT) Proceedings Publication: Accepted academic papers will be published by I...
16 - 18 Oct 2025
Shenyang, China
OCT
17
ICBSP 2025
2025 10th International Conference on Biomedical Imaging, Signal Processing (ICBSP 2025) Paper Publication: 1. ICBSP 2025 SPIE Conference Proceedings: indexed by Ei Compendex and Scopus, and submitted to be reviewed by CPCI. 2. Journal of Image and Graphics (JOIG, ISSN: 2301-3699), Cite Score: 4.1, which wil...
2025 10th International Conference on Biomedical Imaging, Signal Processing (ICBSP 2025) Paper Publication: 1. ICBSP 2025 SPIE Conference Proceedings: indexed by Ei Compendex and Scopus, and submitted to be reviewed by CPCI. 2. Journa...
2025 10th International Conference on Biomedical Imaging, Signal Processing (ICBSP 2025) Paper Publication: 1. ICBSP 2025 SPIE Conference Proceedings: indexed by...
17 - 19 Oct 2025
Xiamen, China
OCT
17
ICICM 2025
2025 The 10th International Conference on Integrated Circuits and Microsystems (ICICM 2025) Publication: The accepted and registered papers will be publication in Conference Proceedings, which will be indexed by EI Compendex, Scopus, etc.
2025 The 10th International Conference on Integrated Circuits and Microsystems (ICICM 2025) Publication: The accepted and registered papers will be publication in Conference Proceedings, which will be indexed by EI Compendex, Scopus, etc.
2025 The 10th International Conference on Integrated Circuits and Microsystems (ICICM 2025) Publication: The accepted and registered papers will be publication in C...
17 - 19 Oct 2025
Hefei, China
OCT
17
ICPEES2025
2025 2nd International Conference on Power Electronics and Energy System (ICPEES 2025) After a careful reviewing process, all accepted papers after proper registration and presentation, will be published in The ICPEES 2025 Conference Proceedings. The proceedings will be submitted to Engineering Village, Scop...
2025 2nd International Conference on Power Electronics and Energy System (ICPEES 2025) After a careful reviewing process, all accepted papers after proper registration and presentation, will be published in The ICPEES 2025 Conference ...
2025 2nd International Conference on Power Electronics and Energy System (ICPEES 2025) After a careful reviewing process, all accepted papers after proper regis...
17 - 19 Oct 2025
Bangkok, Thailand
OCT
18
AIMLNET 2025
5th International conference on AI, Machine Learning in Communications and Networks (AIMLNET 2025) 5th International conference on AI, Machine Learning in Communications and Networks (AIMLNET 2025) October 18 -19, 2025 ,Sydney, Australia https://csty2025.org/aimlnet/index Scope & Topics 5th International conferen...
5th International conference on AI, Machine Learning in Communications and Networks (AIMLNET 2025) 5th International conference on AI, Machine Learning in Communications and Networks (AIMLNET 2025) October 18 -19, 2025 ,Sydney, Australia https...
5th International conference on AI, Machine Learning in Communications and Networks (AIMLNET 2025) 5th International conference on AI, Machine Learning in Communications a...
18 - 19 Oct 2025
Sydney, Australia, Australia
OCT
20
NANOP 2025
NANOP 2025: Functional Nanophotonics After tremendous endeavors, Nanophotonics has already departed from its infancy and stepped into an exciting era, where research ideas and theoretical concepts are being vigorously transferred into functional devices and r...
NANOP 2025: Functional Nanophotonics After tremendous endeavors, Nanophotonics has already departed from its infancy and stepped into an exciting era, where research ideas and theoreti...
NANOP 2025: Functional Nanophotonics After tremendous endeavors, Nanophotonics has already departed from its i...
NANOP 2025: Functional Nanophotonics After tremendous endeavors, Nanophotonics has al...
20 - 22 Oct 2025
Paris, France
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...
23 - 25 Oct 2025
Chongqing, China