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]
|
Text
2107.14126v1.pdf - Submitted version Download (1MB) | Preview |
Abstract
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: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3132584 |
Share
Share
