---
res:
  bibo_abstract:
  - "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.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Krishnendu
      foaf_name: Chatterjee, Krishnendu
      foaf_surname: Chatterjee
      foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-4561-241X
  - foaf_Person:
      foaf_givenName: Rasmus
      foaf_name: Ibsen-Jensen, Rasmus
      foaf_surname: Ibsen-Jensen
      foaf_workInfoHomepage: http://www.librecat.org/personId=3B699956-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0003-4783-0389
  - foaf_Person:
      foaf_givenName: Andreas
      foaf_name: Pavlogiannis, Andreas
      foaf_surname: Pavlogiannis
      foaf_workInfoHomepage: http://www.librecat.org/personId=49704004-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-8943-0722
  bibo_doi: 10.15479/AT:IST-2014-187-v1-1
  dct_date: 2014^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/2664-1690
  dct_language: eng
  dct_publisher: IST Austria@
  dct_title: Improved algorithms for reachability and shortest path on low tree-width
    graphs@
...