Melola Discovery

← Melola Discovery

Akses terbuka Jurnal SINTA 1

A Path-Compression Approach for Improving Shortest-Path Algorithms

International Journal of Electrical and Computer Engineering (IJECE) · Vol. 5 No. 4 (2015)

DOI
10.11591/ijece.v5i4.pp772-781
ISSN
2088-8708, 2088-8708
Terbit
2015-08-01
Penerbit
Institute of Advanced Engineering and Science
Lisensi
creativecommons.org/licenses/by-nc/4.0

Abstrak

Given a weighted directed graph G=(V;E;w), where w is non-negative weight function, G’ is a graph obtained from G by an application of path compression. Path compression reduces the graph G to a critical set of vertices and edges that affect the generation of shortest trees. The main contribution of this paper is finding shortest path between two selected vertices by applying a new algorithm that reduces number of nodes that needs to be traversed in the graph while preserving all graph properties. The main method of the algorithm is restructuring the graph in a way that only critical/relevant nodes are considered while all other neutral vertices and weights are preserved as sub paths' properties. Our algorithm can compress the graph paths into considerable improved percentage especially when the graph is sparse and hence improves performance significantly.

Jaringan kolaborasi para penulis

2 penulis · 1 tautan kepenulisan bersama

Arahkan kursor atau ketuk sebuah nama untuk menyorot rekan penulisnya. Klik dua kali untuk membuka halaman penulis.

  • Palestine Polytechnic University
  • Organisasi berbeda
  • Organisasi sama
  • Afiliasi tidak diketahui
  • Garis lebih tebal = lebih banyak artikel bersama · lingkaran lebih besar = lebih banyak artikel
Tampilkan sebagai tabel
Rekan penulisOrganisasiArtikel bersama

Afiliasi berasal dari OpenAlex; metadata OAI-PMH jurnal tidak memuatnya. Penulis tanpa ID OpenAlex dicocokkan berdasarkan nama, sehingga dua orang bisa tergabung atau satu orang bisa terpisah.

Data ini berasal dari Crossref (yang disetorkan penerbit), karena endpoint OAI-PMH milik jurnal tidak dapat di-harvest.

Sumber metadata: Crossref API (cadangan, berdasarkan ISSN) https://api.crossref.org/journals/2088-8708/works, pertama di-harvest 27 Okt 2026, terakhir terlihat 15 Nov 2026.
Metadata sebagai oai_dc, dikonversi dari Crossref
<oai_dc:dc xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/"><dc:title>A Path-Compression Approach for Improving Shortest-Path Algorithms</dc:title><dc:creator>Arman, Nabil</dc:creator><dc:creator>Khamayseh, Faisal</dc:creator><dc:description>&lt;jats:p&gt;Given a weighted directed graph G=(V;E;w), where w is non-negative weight function, G’ is a graph obtained from G by an application of path compression. Path compression reduces the graph G to a critical set of vertices and edges that affect the generation of shortest trees. The main contribution of this paper is finding shortest path between two selected vertices by applying a new algorithm that reduces number of nodes that needs to be traversed in the graph while preserving all graph properties.  The main method of the algorithm is restructuring the graph in a way that only critical/relevant nodes are considered while all other neutral vertices and weights are preserved as sub paths' properties.  Our algorithm can compress the graph paths into considerable improved percentage especially when the graph is sparse and hence improves performance significantly.&lt;/jats:p&gt;</dc:description><dc:publisher>Institute of Advanced Engineering and Science</dc:publisher><dc:date>2015-08-01</dc:date><dc:type>info:eu-repo/semantics/article</dc:type><dc:format>application/pdf</dc:format><dc:identifier>https://doi.org/10.11591/ijece.v5i4.pp772-781</dc:identifier><dc:identifier>10.11591/ijece.v5i4.pp772-781</dc:identifier><dc:source>International Journal of Electrical and Computer Engineering (IJECE); Vol 5 No 4 (2015); 772</dc:source><dc:source>2088-8708</dc:source><dc:source>2088-8708</dc:source><dc:relation>http://ijece.iaescore.com/index.php/IJECE/article/viewFile/5672/4639</dc:relation><dc:rights>http://creativecommons.org/licenses/by-nc/4.0</dc:rights></oai_dc:dc>