Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.00227 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929445853462528 |
|---|---|
| author | Wan, Joy Z. |
| author_facet | Wan, Joy Z. |
| contents | A Monge directed acyclic graph (DAG) $G$ on the nodes $1,2,\cdots,N$ has edges $\left( i,j\right) $ for $1\leq i<j\leq N$ carrying submodular edge-lengths. Finding a shortest $M$-link path from $1$ to $N$ in $G$ for any given $1<M<N-1$ has many applications. In this paper, we give a contract-and-conquer algorithm for this problem which runs in $O\left( \sqrt{NM\left( N-M\right) \log\left( N-M\right) }\right) $ time and $O\left( N\right) $ space. It is the first $o\left( NM\right) $-time algorithm with linear space complexity, and its time complexity decreases with $M$ when $M\geq N/2$. In contrast, all previous strongly polynomial algorithms have running time growing with $M$. For both $O\left( poly\left( \log N\right) \right) $ and $N-O\left( poly\left( \log N\right) \right) $ regimes of $M$, our algorithm has running time $O\left( N\cdot poly\left( \log N\right) \right) $, which partially answers an open question rased in \cite{AST94} affirmatively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_00227 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Finding a Shortest $M$-link Path in a Monge Directed Acyclic Graph Wan, Joy Z. Data Structures and Algorithms A Monge directed acyclic graph (DAG) $G$ on the nodes $1,2,\cdots,N$ has edges $\left( i,j\right) $ for $1\leq i<j\leq N$ carrying submodular edge-lengths. Finding a shortest $M$-link path from $1$ to $N$ in $G$ for any given $1<M<N-1$ has many applications. In this paper, we give a contract-and-conquer algorithm for this problem which runs in $O\left( \sqrt{NM\left( N-M\right) \log\left( N-M\right) }\right) $ time and $O\left( N\right) $ space. It is the first $o\left( NM\right) $-time algorithm with linear space complexity, and its time complexity decreases with $M$ when $M\geq N/2$. In contrast, all previous strongly polynomial algorithms have running time growing with $M$. For both $O\left( poly\left( \log N\right) \right) $ and $N-O\left( poly\left( \log N\right) \right) $ regimes of $M$, our algorithm has running time $O\left( N\cdot poly\left( \log N\right) \right) $, which partially answers an open question rased in \cite{AST94} affirmatively. |
| title | Finding a Shortest $M$-link Path in a Monge Directed Acyclic Graph |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.00227 |