On the treewidth of dynamic graphs

DOI10.1016/j.tcs.2013.12.024zbMath1381.68225OpenAlexW1939628952MaRDI QIDQ744102

Bernard Mans, Luke Mathieson

Publication date: 6 October 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.12.024

zbMATH Keywords

treewidthdynamic graphslocal treewidthbounded expansionmetatheorems

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Descriptive complexity and finite models (68Q19)

Related Items (3)

As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Computing parameters of sequence-based dynamic graphs ⋮ Sharp lower and upper bounds for the Gaussian rank of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characterisations and examples of graph classes with bounded expansion
• On the fixed-parameter tractability of parameterized model-checking problems
• Maintaining regular properties dynamically in \(k\)-terminal graphs
• Dynamic algorithms for graphs of bounded treewidth
• Ad-hoc, mobile, and wireless networks. Second international conference ADHOC-NOW 2003, Montreal, Canada, October 8--10, 2003. Proceedings.
• On the exploration of time-varying networks
• On nowhere dense graphs
• Parametrized complexity theory.
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Distributed computation in dynamic networks
• The Complexity of Data Aggregation in Directed Networks
• Deterministic Computations in Time-Varying Graphs: Broadcasting under Unstructured Mobility
• Deciding first-order properties of locally tree-decomposable structures
• Characterizing Topological Assumptions of Distributed Algorithms in Dynamic Networks
• On the Treewidth of Dynamic Graphs
• Information Propagation Speed in Mobile and Delay Tolerant Networks
• The monadic second-order logic of graphs XVI : Canonical graph decompositions
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Connectivity and inference problems for temporal networks

This page was built for publication: On the treewidth of dynamic graphs