<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE ArticleSet PUBLIC "-//NLM//DTD PubMed 2.7//EN" "https://dtd.nlm.nih.gov/ncbi/pubmed/in/PubMed.dtd">
<ArticleSet>
<Article>
<Journal>
				<PublisherName>University of Isfahan</PublisherName>
				<JournalTitle>Transactions on Combinatorics</JournalTitle>
				<Issn>2251-8657</Issn>
				<Volume>5</Volume>
				<Issue>3</Issue>
				<PubDate PubStatus="epublish">
					<Year>2016</Year>
					<Month>09</Month>
					<Day>01</Day>
				</PubDate>
			</Journal>
<ArticleTitle>A new $O(m+k n \log \overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs</ArticleTitle>
<VernacularTitle></VernacularTitle>
			<FirstPage>23</FirstPage>
			<LastPage>31</LastPage>
			<ELocationID EIdType="pii">12602</ELocationID>
			
<ELocationID EIdType="doi">10.22108/toc.2016.12602</ELocationID>
			
			<Language>EN</Language>
<AuthorList>
<Author>
					<FirstName>Mehdi</FirstName>
					<LastName>Kadivar</LastName>
<Affiliation>Academic member of Shahrekord University</Affiliation>

</Author>
</AuthorList>
				<PublicationType>Journal Article</PublicationType>
			<History>
				<PubDate PubStatus="received">
					<Year>2015</Year>
					<Month>07</Month>
					<Day>25</Day>
				</PubDate>
			</History>
		<Abstract>‎We give an algorithm‎, ‎called T$^{*}$‎, ‎for finding the &lt;em&gt;k&lt;/em&gt; shortest simple paths connecting a certain‎ ‎pair of nodes‎, ‎$s$ and $t$‎, ‎in a acyclic digraph‎. ‎First the nodes of the graph are labeled according to the topological ordering‎. ‎Then for node $i$ an ordered list of simple $s-i$ paths is created‎. ‎The length of the list is at most $k$ and it is created by using tournament trees‎. ‎We prove the correctness of T$^{*}$ and show that its worst-case complexity is $O(m+k n \log \overline{d})$ in which&lt;em&gt; n&lt;/em&gt; is the number of nodes and &lt;em&gt;m&lt;/em&gt; is the number of arcs and $\overline{d}$ is the mean degree of the graph‎. ‎The algorithm has a space complexity of $O(kn)$ which entails an important improvement in space complexity‎. ‎An experimental evaluation of T$^{*}$ is presented which confirms the advantage of our algorithm compared to the‎ ‎most efficient $k$ shortest paths algorithms known so far‎.</Abstract>
		<ObjectList>
			<Object Type="keyword">
			<Param Name="value">$k$ shortest path problem‎</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">‎complexity of algorithms‎</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">‎ranking of paths</Param>
			</Object>
		</ObjectList>
<ArchiveCopySource DocType="pdf">https://toc.ui.ac.ir/article_12602_8c4b300132a9c7b4f66cb1e49e80f1c2.pdf</ArchiveCopySource>
</Article>
</ArticleSet>
