On the Complexity of Local Graph Transformations

DOI10.4230/LIPIcs.ICALP.2019.150OpenAlexW2965977219MaRDI QIDQ5092357

Alexander Setzer, Christian Scheideler

Publication date: 21 July 2022

Full work available at URL: https://arxiv.org/abs/1904.11395

zbMATH Keywords

approximation algorithmsNP-hardnessgraphs transformations

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items (2)

Distributed computation and reconfiguration in actively dynamic networks ⋮ The complexity of growing a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Building self-stabilizing overlay networks with the transitive closure framework
• Corona: a stabilizing deterministic message-passing skip list
• Towards higher-dimensional topological self-stabilization: a distributed algorithm for Delaunay graphs
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Graph transformation for specification and programming
• HyperTree for self-stabilizing peer-to-peer systems
• Towards a universal approach for the finite departure problem in overlay networks
• Basic Network Creation Games
• Greedy Algorithms for Steiner Forest
• On a network creation game
• On nash equilibria for a network creation game
• Handbook of Graph Grammars and Computing by Graph Transformation
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Basic Network Creation Games with Communication Interests
• A Local-Search Algorithm for Steiner Forest
• The price of anarchy in network creation games
• SKIP ⁺
• The complexity of theorem-proving procedures

This page was built for publication: On the Complexity of Local Graph Transformations