The Complexity of Growing a Graph

Mertzios, George B, Michail, Othon ORCID: 0000-0002-6234-3960, Skretas, George ORCID: 0000-0003-2514-8004, Spirakis, Paul G ORCID: 0000-0001-5396-3749 and Theofilatos, Michail ORCID: 0000-0002-3699-0179
(2021) The Complexity of Growing a Graph. [Preprint]

[img] Text
2107.14126v1.pdf - Submitted version

Download (1MB) | Preview


We study a new algorithmic process of graph growth which starts from a single initial vertex and operates in discrete time-steps, called \emph{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 \emph{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 \emph{growth schedule}. Additionally, the algorithm should try to minimize the total number of slots $k$ and of excess edges $\ell$ used by the process. We provide both positive and negative results for different values of $k$ and $\ell$, with our main focus being either schedules with sub-linear number of slots or with zero excess edges.

Item Type: Preprint
Additional Information: 30 pages
Uncontrolled Keywords: cs.DS, cs.DS, cs.CC
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 09 Aug 2021 08:36
Last Modified: 18 Jan 2023 21:33
Related URLs: