Cited By
View all- Oliver DXu BPao Y(2019)ACM SIGSPATIAL cup 2018 - identifying upstream features in large spatial networksSIGSPATIAL Special10.1145/3355491.335549811:1(32-35)Online publication date: 5-Aug-2019
Wüpstream: efficient enumeration of upstream features (GIS cup)
Authors: 
Thomas C. van Dijk, Tobias Greiner, Bas den Heijer, Nadja Henning, Felix Klesen, Andre LöfflerAuthors Info & Claims
Thomas C. van Dijk, Tobias Greiner, Bas den Heijer, Nadja Henning, Felix Klesen, Andre LöfflerAuthors Info & ClaimsPages 626 - 629
Abstract
This short paper describes Wüpstream, an efficient code for enumerating upstream features in undirected graphs. It uses a linear-time algorithm based on block-cut trees. We describe this algorithm and discuss some performance considerations in the C++ implementation. Code is available at: https://github.com/tcvdijk/wupstream.
References
[1]
Raymond Chen. 2012. When DLL-PROCESS-DETACH tells you that the process is exiting, your best bet is just to return without doing anything. https://blogs.msdn.microsoft.com/oldnewthing/20120105-00.
[2]
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press.
[3]
David R. Hanson. 1990. Fast allocation and deallocation of memory based on object lifetimes. Software: Practice and Experience 20, 1 (1990), 5--12.
[4]
F. Harary. 1969. Graph theory. Addison-Wesley Pub. Co.
[5]
Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. 2001. Poly-logarithmic Deterministic Fully-dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-edge, and Biconnectivity. J. ACM 48, 4 (July 2001), 723--760.
[6]
John Hopcroft and Robert Tarjan. 1973. Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16, 6 (1973), 372--378.
[7]
Yinan Li, Nikos R. Katsipoulakis, Badrish Chandramouli, Jonathan Goldstein, and Donald Kossmann. 2017. Mison: A Fast JSON Parser for Data Analytics. In The 43rd International Conference on Very Large Data Bases (VLDB 2017).
[8]
Milo Yip and THL A29 Limited, a Tencent company. 2015. RapidJSON. http://rapidjson.org/.
Index Terms
- Wüpstream: efficient enumeration of upstream features (GIS cup)
Recommendations
L(2,1)-labeling of dually chordal graphs and strongly orderable graphs
An L(2,1)-labeling of a graph G=(V,E) is a function f:V(G)->{0,1,2,...} such that |f(u)-f(v)|>=2 whenever uv@__ __E(G) and |f(u)-f(v)|>=1 whenever u and v are at distance two apart. The span of an L(2,1)-labeling f of G, denoted as SP"2(f,G), is the ...
3-colouring for dually chordal graphs and generalisations
In this paper, we investigate the Colourability problem for dually chordal graphs and some of its generalisations. We show that the problem remains NP-complete if limited to four colours. For the case of three colours, we present a simple linear time ...
Computing a minimum outer-connected dominating set for the class of chordal graphs
For a graph G=(V,E), a dominating set is a set D@?V such that every vertex v@?V@?D has a neighbor in D. Given a graph G=(V,E) and a positive integer k, the minimum outer-connected dominating set problem for G is to decide whether G has a dominating set ...
Comments
Information & Contributors
Information
Published In
November 2018
655 pages
ISBN:9781450358897
DOI:10.1145/3274895
- General Chairs:
- Farnoush Banaei-Kashani,
- Erik Hoel,
- Program Chairs:
- Ralf Hartmut Güting,
- Roberto Tamassia,
- Li Xiong
Copyright © 2018 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 06 November 2018
Check for updates
Author Tags
Qualifiers
- Short-paper
Funding Sources
Conference
SIGSPATIAL '18
Sponsor:
SIGSPATIAL '18: 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
November 6 - 9, 2018
Washington, Seattle
Acceptance Rates
SIGSPATIAL '18 Paper Acceptance Rate 30 of 150 submissions, 20%;
Overall Acceptance Rate 220 of 1,116 submissions, 20%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 89Total Downloads
- Downloads (Last 12 months)9
- Downloads (Last 6 weeks)2
Reflects downloads up to 15 Sep 2024
Other Metrics
Citations
Cited By
View all- Oliver DXu BPao Y(2019)ACM SIGSPATIAL cup 2018 - identifying upstream features in large spatial networksSIGSPATIAL Special10.1145/3355491.335549811:1(32-35)Online publication date: 5-Aug-2019
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in