As Time Goes By: Reflections on Treewidth for Temporal Graphs

DOI10.1007/978-3-030-42071-0_6OpenAlexW3105336953MaRDI QIDQ5042450

Till Fluschnik, Hendrik Molter, Philipp Zschoche, Rolf Niedermeier, Malte Renken

Publication date: 19 October 2022

Published in: Treewidth, Kernels, and Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

tree decompositionNP-hardnessparameterized complexitynetwork sciencelink streamtime-evolving networkmonadic second-order logic (MSO)

Mathematics Subject Classification ID

Computer science (68-XX)

Related Items

Mengerian graphs: characterization and recognition ⋮ Coloring temporal graphs ⋮ Feedback edge sets in temporal graphs ⋮ Edge exploration of temporal graphs ⋮ Edge exploration of temporal graphs ⋮ On finding separators in temporal split and permutation graphs

Uses Software

• ComputeTW
• cliques

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Treewidth computations. II. Lower bounds
• On the treewidth of dynamic graphs
• On bounded-degree vertex deletion parameterized by treewidth
• Computing maximal cliques in link streams
• The Steiner forest problem revisited
• Complexity results for minimum sum edge coloring
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• A constructive proof of Vizing's theorem
• Graph searching and a min-max theorem for tree-width
• Treewidth. Computations and approximations
• Treewidth for graphs with small chordality
• On exploring always-connected temporal graphs of small pathwidth
• Parameterized complexity of length-bounded cuts and multicuts
• On the exploration of time-varying networks
• Finding temporal paths under waiting time constraints
• The complexity of finding small separators in temporal graphs
• Temporal vertex cover with a sliding time window
• Sliding window temporal graph coloring
• Multistage vertex cover
• Assigning times to minimise reachability in temporal graphs
• The parameterized complexity of the minimum shared edges problem
• Parametrized complexity theory.
• On temporal graph exploration
• Optimizing reachability sets in temporal graphs by delaying
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• A Game of Cops and Robbers on Graphs with Periodic Edge-Connectivity
• Easy problems for tree-decomposable graphs
• Capacitated Domination and Covering: A Parameterized Perspective
• Complexity of Finding Embeddings in a k-Tree
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs
• On the Size and the Approximability of Minimum Temporally Connected Subgraphs
• The Pathwidth and Treewidth of Cographs
• Treewidth and Pathwidth of Permutation Graphs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Temporal Cliques Admit Sparse Spanners
• NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Computing maximum matchings in temporal graphs.
• Temporal graph classes: a view through temporal separators
• The temporal explorer who returns to the base
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Dynamic algorithms for graphs with treewidth 2

This page was built for publication: As Time Goes By: Reflections on Treewidth for Temporal Graphs