---
_id: '5419'
abstract:
- lang: eng
  text: "We consider the reachability and shortest path problems on low tree-width
    graphs, with n nodes, m edges, and tree-width t, on a standard RAM with wordsize
    W. We use O to hide polynomial factors of the inverse of the Ackermann function.
    Our main contributions are three fold:\r\n1. For reachability, we present an algorithm
    that requires O(n·t2·log(n/t)) preprocessing time, O(n·(t·log(n/t))/W) space,
    and O(t/W) time for pair queries and O((n·t)/W) time for single-source queries.
    Note that for constant t our algorithm uses O(n·logn) time for preprocessing;
    and O(n/W) time for single-source queries, which is faster than depth first search/breath
    first search (after the preprocessing).\r\n2. We present an algorithm for shortest
    path that requires O(n·t2) preprocessing time, O(n·t) space, and O(t2) time for
    pair queries and O(n·t) time single-source queries.\r\n3. We give a space versus
    query time trade-off algorithm for shortest path that, given any constant >0,
    requires O(n·t2) preprocessing time, O(n·t2) space, and O(n1−·t2) time for pair
    queries.\r\nOur algorithms improve all existing results, and use very simple data
    structures."
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Rasmus
  full_name: Ibsen-Jensen, Rasmus
  id: 3B699956-F248-11E8-B48F-1D18A9856A87
  last_name: Ibsen-Jensen
  orcid: 0000-0003-4783-0389
- first_name: Andreas
  full_name: Pavlogiannis, Andreas
  id: 49704004-F248-11E8-B48F-1D18A9856A87
  last_name: Pavlogiannis
  orcid: 0000-0002-8943-0722
citation:
  ama: Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. <i>Improved Algorithms for Reachability
    and Shortest Path on Low Tree-Width Graphs</i>. IST Austria; 2014. doi:<a href="https://doi.org/10.15479/AT:IST-2014-187-v1-1">10.15479/AT:IST-2014-187-v1-1</a>
  apa: Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2014). <i>Improved
    algorithms for reachability and shortest path on low tree-width graphs</i>. IST
    Austria. <a href="https://doi.org/10.15479/AT:IST-2014-187-v1-1">https://doi.org/10.15479/AT:IST-2014-187-v1-1</a>
  chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis.
    <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>.
    IST Austria, 2014. <a href="https://doi.org/10.15479/AT:IST-2014-187-v1-1">https://doi.org/10.15479/AT:IST-2014-187-v1-1</a>.
  ieee: K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, <i>Improved algorithms
    for reachability and shortest path on low tree-width graphs</i>. IST Austria,
    2014.
  ista: Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Improved algorithms for
    reachability and shortest path on low tree-width graphs, IST Austria, 34p.
  mla: Chatterjee, Krishnendu, et al. <i>Improved Algorithms for Reachability and
    Shortest Path on Low Tree-Width Graphs</i>. IST Austria, 2014, doi:<a href="https://doi.org/10.15479/AT:IST-2014-187-v1-1">10.15479/AT:IST-2014-187-v1-1</a>.
  short: K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Improved Algorithms for
    Reachability and Shortest Path on Low Tree-Width Graphs, IST Austria, 2014.
date_created: 2018-12-12T11:39:13Z
date_published: 2014-04-14T00:00:00Z
date_updated: 2021-01-12T08:02:03Z
day: '14'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-187-v1-1
file:
- access_level: open_access
  checksum: c608e66030a4bf51d2d99b451f539b99
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T11:54:25Z
  date_updated: 2020-07-14T12:46:50Z
  file_id: '5548'
  file_name: IST-2014-187-v1+1_main_full_tech.pdf
  file_size: 670031
  relation: main_file
file_date_updated: 2020-07-14T12:46:50Z
has_accepted_license: '1'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: '34'
publication_identifier:
  issn:
  - 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '187'
status: public
title: Improved algorithms for reachability and shortest path on low tree-width graphs
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...