On the Complexity of Local Graph Transformations

DOI10.4230/LIPICS.ICALP.2019.150MaRDI QIDQ5092357zbMATH OpenOpenAlexFDO

Authors Alexander Setzer, Christian Scheideler

Publication date 21 July 2022

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

zbMATH Keywords

approximation algorithmsgraphs transformationsNP-hardness

Mathematics Subject Classification ID

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

Recommendations

• The minimum-cost transformation of graphs
• On limitations of transformations between combinatorial problems
• Parallel Graph Rewriting with Overlapping Rules
• Linear algorithm for a cyclic graph transformation
• scientific article; zbMATH DE number 512941

Cites work

• \(\mathrm{SKIP}^{+}\), a self-stabilizing skip graph
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A General Approximation Technique for Constrained Forest Problems
• A local-search algorithm for Steiner forest
• Basic network creation games
• Basic network creation games with communication interests
• Building self-stabilizing overlay networks with the transitive closure framework
• Corona: a stabilizing deterministic message-passing skip list
• Graph transformation for specification and programming
• Greedy algorithms for Steiner forest
• Handbook of Graph Grammars and Computing by Graph Transformation
• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• scientific article; zbMATH DE number 1555923 (Why is no real title available?)
• scientific article; zbMATH DE number 1437942 (Why is no real title available?)
• HyperTree for self-stabilizing peer-to-peer systems
• On a network creation game
• On nash equilibria for a network creation game
• The complexity of theorem-proving procedures
• The price of anarchy in network creation games
• Towards a universal approach for the finite departure problem in overlay networks
• Towards higher-dimensional topological self-stabilization: a distributed algorithm for Delaunay graphs
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(9)

• Distributed computation and reconfiguration in actively dynamic networks
• Towards Local Confluence Analysis for Amalgamated Graph Transformation
• On Local Expansion of Vertex-Transitive Graphs
• scientific article; zbMATH DE number 2087494 (Why is no real title available?)
• scientific article; zbMATH DE number 7308467 (Why is no real title available?)
• Node and edge averaged complexities of local graph problems
• The complexity of growing a graph
• The complexity of growing a graph
• Robust overlays meet blockchains: on handling high churn and catastrophic failures

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5092357)