Temporal graph classes: a view through temporal separators

DOI10.1007/978-3-030-00256-5_18zbMath1436.68235arXiv1803.00882OpenAlexW3215520283WikidataQ128176012 ScholiaQ128176012MaRDI QIDQ5915590

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

Publication date: 22 November 2018

Published in: Theoretical Computer Science, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programmingNP-completenessfixed-parameter tractabilitytemporal pathstemporal restrictionsunit-interval graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (30)

As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ On exploring always-connected temporal graphs of small pathwidth ⋮ Multistage vertex cover ⋮ Mengerian temporal graphs revisited ⋮ Deleting edges to restrict the size of an epidemic in temporal networks ⋮ Temporal interval cliques and independent sets ⋮ Non-strict Temporal Exploration ⋮ Mengerian graphs: characterization and recognition ⋮ Simple, strict, proper, happy: a study of reachability in temporal graphs ⋮ Sharp Thresholds in Random Simple Temporal Graphs ⋮ Invited paper: Simple, strict, proper, happy: a study of reachability in temporal graphs ⋮ Untangling temporal graphs of bounded degree ⋮ Unnamed Item ⋮ Assigning times to minimise reachability in temporal graphs ⋮ Finding temporal paths under waiting time constraints ⋮ The Complexity of Finding Small Separators in Temporal Graphs ⋮ Coloring temporal graphs ⋮ Finding Temporal Paths Under Waiting Time Constraints. ⋮ Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs ⋮ Unnamed Item ⋮ Temporal graph classes: a view through temporal separators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sliding window temporal graph coloring ⋮ Temporal cliques admit sparse spanners ⋮ Feedback edge sets in temporal graphs ⋮ On finding separators in temporal split and permutation graphs ⋮ On finding separators in temporal split and permutation graphs ⋮ A faster parameterized algorithm for temporal matching ⋮ The complexity of finding temporal separators under waiting time constraints

Cites Work

• Unnamed Item
• Traveling salesman problems in temporal graphs
• Fundamentals of parameterized complexity
• Sparsity. Graphs, structures, and algorithms
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Parameterized complexity of vertex colouring
• On the exploration of time-varying networks
• Optimal greedy algorithms for indifference graphs
• The complexity of optimal design of temporally connected graphs
• Temporal flows in temporal networks
• Parametrized complexity theory.
• On temporal graph exploration
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Distributed computation in dynamic networks
• Graph Classes: A Survey
• On the Size and the Approximability of Minimum Temporally Connected Subgraphs
• The Complexity of Finding Small Separators in Temporal Graphs
• Parameterized and Exact Computation
• Temporal Network Optimization Subject to Connectivity Constraints
• Parameterized Algorithms
• Characterizations of derived graphs
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• A NEW MEASURE OF RANK CORRELATION
• An Introduction to Temporal Graphs: An Algorithmic Perspective^*
• Connectivity and inference problems for temporal networks
• Temporal graph classes: a view through temporal separators

This page was built for publication: Temporal graph classes: a view through temporal separators