The complexity of growing a graph
DOI10.1016/j.jcss.2024.103587MaRDI QIDQ6627045
Paul G. Spirakis, George B. Mertzios, Othon Michail, George Skretas, Michail Theofilatos
Publication date: 29 October 2024
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
NP-completenesslower boundpolynomial-time algorithmhardness resultcop-win graphdynamic graphtemporal graphgraph process
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games on graphs (graph-theoretic aspects) (05C57)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Arboricity, \(h\)-index, and dynamic algorithms
- Clique graphs and Helly graphs
- Temporal network optimization subject to connectivity constraints
- On the transformation capability of feasible mechanisms for programmable matter
- The complexity of finding small separators in temporal graphs
- Temporal vertex cover with a sliding time window
- Distributed computation and reconfiguration in actively dynamic networks
- Faster construction of overlay networks
- Adaptive energy management for incremental deployment of heterogeneous wireless sensors
- Deleting edges to restrict the size of an epidemic in temporal networks
- Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
- Emergence of Scaling in Random Networks
- On Distance-Preserving and Domination Elimination Orderings
- Skip graphs
- On the Complexity of Local Graph Transformations
- DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead
- An Introduction to Temporal Graphs: An Algorithmic Perspective*
- Connectivity and inference problems for temporal networks
- Time-optimal construction of overlay networks
- The complexity of growing a graph
This page was built for publication: The complexity of growing a graph
