{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T06:34:42Z","timestamp":1774506882511,"version":"3.50.1"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,6]]},"abstract":"<jats:p>\n            For a directed graph\n            <jats:italic>G<\/jats:italic>\n            with vertex set\n            <jats:italic>V<\/jats:italic>\n            we call a subset\n            <jats:italic>C<\/jats:italic>\n            \u2286\n            <jats:italic>V<\/jats:italic>\n            a\n            <jats:italic>k-(All-)Path Cover<\/jats:italic>\n            if\n            <jats:italic>C<\/jats:italic>\n            contains a node from\n            <jats:italic>any<\/jats:italic>\n            path consisting of\n            <jats:italic>k<\/jats:italic>\n            nodes. This paper considers the problem of constructing small\n            <jats:italic>k<\/jats:italic>\n            -Path Covers in the context of road networks with millions of nodes and edges. In many application scenarios the set\n            <jats:italic>C<\/jats:italic>\n            and its induced overlay graph constitute a very compact synopsis of\n            <jats:italic>G<\/jats:italic>\n            which is the basis for the currently fastest data structure for personalized shortest path queries, visually pleasing overlays of subsampled paths, and efficient reporting, retrieval and aggregation of associated data in spatial network databases. Apart from a theoretical investigation of the problem, we provide efficient algorithms that produce very small\n            <jats:italic>k<\/jats:italic>\n            -Path Covers for large real-world road networks (with a posteriori guarantees via instance-based lower bounds).\n          <\/jats:p>","DOI":"10.14778\/2732951.2732963","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"893-902","source":"Crossref","is-referenced-by-count":34,"title":["On k-path covers and their applications"],"prefix":"10.14778","volume":"7","author":[{"given":"Stefan","family":"Funke","sequence":"first","affiliation":[{"name":"Universit\u00e4t Stuttgart Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Nusser","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Stuttgart Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sabine","family":"Storandt","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Freiburg Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2027127.2027200"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2008623.2008645"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1137521"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.04.008"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570718"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2008623.2008657"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972931.4"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1110.0401"},{"key":"e_1_2_1_9_1","first-page":"100","volume-title":"Algorithm Engineering and Experiments (ALENEX)","author":"Gutman R. J.","year":"2004","unstructured":"R. J. Gutman . Reach-based routing : A new approach to shortest path algorithms optimized for road networks . In Algorithm Engineering and Experiments (ALENEX) , pages 100 -- 111 , 2004 . R. J. Gutman. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Algorithm Engineering and Experiments (ALENEX), pages 100--111, 2004."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/10515.10522"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.57"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989368"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2732951.2732963","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:58:38Z","timestamp":1672225118000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2732951.2732963"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6]]},"references-count":13,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["10.14778\/2732951.2732963"],"URL":"https:\/\/doi.org\/10.14778\/2732951.2732963","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,6]]}}}