The complexity of growing a graph
From MaRDI portal
Publication:6112002
DOI10.1007/978-3-031-22050-0_9arXiv2107.14126MaRDI QIDQ6112002
George B. Mertzios, George Skretas, Othon Michail, Paul G. Spirakis, Michail Theofilatos
Publication date: 4 August 2023
Published in: Algorithmics of Wireless Networks (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2107.14126
lower boundpolynomial-time algorithmNP-completehardness resultcop-win graphtemporal graphgraph process
Artificial intelligence for robotics (68T40) Wireless sensor networks as related to computer science (68M18)
Related Items (2)
On geometric shape construction via growth operations ⋮ On geometric shape construction via growth operations
Cites Work
- 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
- 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
- A Linear Algorithm for Colouring Planar Graphs with Five Colours
- Skip graphs
- On the Complexity of Local Graph Transformations
- DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead
- Distributed Computation and Reconfiguration in Actively Dynamic Networks
- An Introduction to Temporal Graphs: An Algorithmic Perspective*
- Connectivity and inference problems for temporal networks
- Time-optimal construction of overlay networks
This page was built for publication: The complexity of growing a graph
