2021/07/29 by George B. Mertzios, Mertzios, George B., Othon Michail +7
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2107.14126
openalex publication_date 2021/07/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study a new algorithmic process of graph growth which starts from a single initial vertex and operates in discrete time-steps, called slots. In every slot, the graph grows via two operations (i) vertex generation and (ii) edge activation. The process completes at the last slot where a (possibly empty) subset of the edges of the graph will be removed. Removed edges are called excess edges. The main problem investigated in this paper is: Given a target graph G, we are asked to design an algorithm that outputs such a process growing G, called a growth schedule. Additionally, the algorithm should try to minimize the total number of slots k and of excess edges ℓ used by the process. We provide both positive and negative results for different values of k and ℓ, with our main focus being either schedules with sub-linear number of slots or with zero excess edges.