On the treewidth of dynamic graphs

DOI10.1016/J.TCS.2013.12.024MaRDI QIDQ744102zbMATHOpenAlexFDO

Authors 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)

Recommendations

• On the treewidth of dynamic graphs
• Dynamic algorithms for graphs of bounded treewidth
• Dynamic graph models
• Dynamic algorithms for graphs of bounded treewidth
• scientific article; zbMATH DE number 4060712

Cites work

• scientific article; zbMATH DE number 1263263 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 961960 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Ad-hoc, mobile, and wireless networks. Second international conference ADHOC-NOW 2003, Montreal, Canada, October 8--10, 2003. Proceedings.
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Characterisations and examples of graph classes with bounded expansion
• Characterizing topological assumptions of distributed algorithms in dynamic networks
• Connectivity and inference problems for temporal networks
• Deciding first-order properties of locally tree-decomposable structures
• Deterministic computations in time-varying graphs: broadcasting under unstructured mobility
• Distributed computation in dynamic networks
• Dynamic algorithms for graphs of bounded treewidth
• Information Propagation Speed in Mobile and Delay Tolerant Networks
• Introduction to mathematical logic
• Maintaining regular properties dynamically in \(k\)-terminal graphs
• On nowhere dense graphs
• On the exploration of time-varying networks
• On the fixed-parameter tractability of parameterized model-checking problems
• On the treewidth of dynamic graphs
• Parametrized complexity theory.
• The complexity of data aggregation in directed networks
• The monadic second-order logic of graphs XVI : Canonical graph decompositions
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(10)

• Dynamic algorithms for graphs of bounded treewidth
• On the computational complexity of dynamic graph problems
• On the treewidth of dynamic graphs
• Dynamic low-stretch trees via dynamic low-diameter decompositions
• As Time Goes By: Reflections on Treewidth for Temporal Graphs
• Minimizing diameters of dynamic trees
• Dynamic algorithms for graphs with treewidth 2
• On Dynamic DFS Tree in Directed Graphs
• Sharp lower and upper bounds for the Gaussian rank of a graph
• Computing parameters of sequence-based dynamic graphs

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

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