The complexity of growing a graph

Mertzios, G.B.; Michail, O.; Skretas, G.; Spirakis, P.G.; Theofilatos, M.

doi:10.1007/978-3-031-22050-0_9

The complexity of growing a graph

Mertzios, G.B.; Michail, O.; Skretas, G.; Spirakis, P.G.; Theofilatos, M.

Authors

Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor

O. Michail

G. Skretas

P.G. Spirakis

M. Theofilatos

Abstract

We study a new algorithmic process of graph growth. The process starts from a single initial vertex u0 and operates in discrete timesteps, called slots. In every slot t ≥ 1, the process updates the current graph instance to generate the next graph instance Gt. The process first sets Gt = Gt−1. Then, for every u ∈ V (Gt−1), it adds at most one new vertex u 0 to V (Gt) and adds the edge uu0 to E(Gt) alongside any subset of the edges {vu0 | v ∈ V (Gt−1) is at distance at most d − 1 from u in Gt−1}, for some integer d ≥ 1 fixed in advance. The process completes slot t after removing any (possibly empty) subset of edges from E(Gt). Removed edges are called excess edges. Gt is the graph grown by the process after t slots. The goal of this paper is to investigate the algorithmic and structural properties of this process of graph growth.

Citation

Mertzios, G., Michail, O., Skretas, G., Spirakis, P., & Theofilatos, M. (2022). The complexity of growing a graph. In ALGOSENSORS 2022: Algorithmics of Wireless Networks (123-137). https://doi.org/10.1007/978-3-031-22050-0_9

Conference Name	18th International Symposium on Algorithmics of Wireless Networks (ALGOSENSORS 2022)
Conference Location	Potsdam, Germany
Start Date	Sep 5, 2022
End Date	Sep 9, 2022
Acceptance Date	Aug 1, 2022
Online Publication Date	Dec 13, 2022
Publication Date	Dec 13, 2022
Deposit Date	Sep 27, 2022
Publicly Available Date	Dec 14, 2023
Publisher	Springer Verlag
Volume	13707
Pages	123-137
Series Title	Lecture Notes in Computer Science
Series ISSN	0302-9743
Book Title	ALGOSENSORS 2022: Algorithmics of Wireless Networks
ISBN	9783031220494
DOI	https://doi.org/10.1007/978-3-031-22050-0_9
Public URL	https://durham-repository.worktribe.com/output/1135702
Additional Information	September 8–9, 2022