Constant-time Connectivity Querying in Dynamic Graphs

Xu, L; Wen, D; Qin, L; Li, R; Zhang, Y; Lin, X

Constant-time Connectivity Querying in Dynamic Graphs

Xu, L

Wen, D

Qin, L

Li, R Zhang, Y

Lin, X

Permalink

Publisher:: Association for Computing Machinery (ACM)
Publication Type:: Journal Article
Citation:: Proceedings of the ACM on Management of Data, 2024, 2, (6), pp. 1-23
Issue Date:: 2024-12-18

Recently Added

	Filename	Description	Size
	Constant-time Connectivity Querying in Dynamic Graphs.pdf	Published version	867.55 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is new to OPUS and is not currently available.

Full metadata record

Field	Value	Language
dc.contributor.author	Xu, L https://orcid.org/0009-0000-9846-8629
dc.contributor.author	Wen, D https://orcid.org/0000-0002-0903-1503
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062
dc.contributor.author	Li, R
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Lin, X
dc.date.accessioned	2025-03-12T03:09:22Z
dc.date.available	2025-03-12T03:09:22Z
dc.date.issued	2024-12-18
dc.identifier.citation	Proceedings of the ACM on Management of Data, 2024, 2, (6), pp. 1-23
dc.identifier.issn	2836-6573
dc.identifier.issn	2836-6573
dc.identifier.uri	http://hdl.handle.net/10453/185723
dc.description.abstract	<jats:p>Connectivity query processing is a fundamental problem in graph processing. Given an undirected graph and two query vertices, the problem aims to identify whether they are connected via a path. Given frequent edge updates in real graph applications, in this paper, we study connectivity query processing in fully dynamic graphs, where edges are frequently inserted or deleted. A recent solution, called D-tree, maintains a spanning tree for each connected component and applies several heuristics to reduce the depth of the tree. To improve the efficiency, we propose a new spanning-tree-based solution by maintaining a disjoint-set tree simultaneously. By combining the advantages of two trees, we achieve the constant query time complexity and also significantly improve the theoretical running time in both edge insertion and edge deletion. Our performance studies on real large datasets show considerable improvement of our algorithms.</jats:p>
dc.language	en
dc.publisher	Association for Computing Machinery (ACM)
dc.relation.ispartof	Proceedings of the ACM on Management of Data
dc.relation.isbasedon	10.1145/3698805
dc.rights	info:eu-repo/semantics/restrictedAccess
dc.title	Constant-time Connectivity Querying in Dynamic Graphs
dc.type	Journal Article
utslib.citation.volume	2
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	University of Technology Sydney/UTS Groups
pubs.organisational-group	University of Technology Sydney/UTS Groups/Australian Artificial Intelligence Institute (AAII)
utslib.copyright.status	recently_added	*
dc.date.updated	2025-03-12T03:09:20Z
pubs.issue	6
pubs.publication-status	Published
pubs.volume	2
utslib.citation.issue	6

Abstract:

Connectivity query processing is a fundamental problem in graph processing. Given an undirected graph and two query vertices, the problem aims to identify whether they are connected via a path. Given frequent edge updates in real graph applications, in this paper, we study connectivity query processing in fully dynamic graphs, where edges are frequently inserted or deleted. A recent solution, called D-tree, maintains a spanning tree for each connected component and applies several heuristics to reduce the depth of the tree. To improve the efficiency, we propose a new spanning-tree-based solution by maintaining a disjoint-set tree simultaneously. By combining the advantages of two trees, we achieve the constant query time complexity and also significantly improve the theoretical running time in both edge insertion and edge deletion. Our performance studies on real large datasets show considerable improvement of our algorithms.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/185723