The complexity of growing a graph

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

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
• Book Title: ALGOSENSORS 2022: Algorithmics of Wireless Networks
• ISBN: 9783031220494
• DOI: https://doi.org/10.1007/978-3-031-22050-0_9
• Additional Information: September 8–9, 2022