Computing maximum matchings in temporal graphs
From MaRDI portal
Publication:6168321
DOI10.1016/j.jcss.2023.04.005MaRDI QIDQ6168321
Hendrik Molter, George B. Mertzios, Philipp Zschoche, Rolf Niedermeier, Victor Zamaraev
Publication date: 10 July 2023
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/11888/
independent setapproximation algorithmsNP-hardnessfixed-parameter tractabilityAPX-hardnesskernelizationlink streamstemporal line graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Unit disk graphs
- Some simplified NP-complete graph problems
- Some APX-completeness results for cubic graphs
- Which problems have strongly exponential complexity?
- Temporal network optimization subject to connectivity constraints
- Online algorithms for maximum cardinality matching with edge arrivals
- Face covers and the genus problem for apex graphs
- 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
- A faster parameterized algorithm for temporal matching
- Maximum 0-1 timed matching on temporal graphs
- Temporal matching
- Complexity of approximating bounded variants of optimization problems
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- Algorithmic aspects of the \(k\)-domination problem in graphs
- On temporal graph exploration
- Temporal matching on geometric graph data
- Graph Theory
- Flooding Time of Edge-Markovian Evolving Graphs
- Universality considerations in VLSI circuits
- K-greedy algorithms for independence systems
- An Analysis of the Greedy Heuristic for Independence Systems
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Bipartite Edge Coloring in $O(\Delta m)$ Time
- Randomized greedy matching. II
- Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
- On the Size and the Approximability of Minimum Temporally Connected Subgraphs
- Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
- Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
- 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
- How fast can we reach a target vertex in stochastic temporal graphs
- Data Reduction for Maximum Matching on Real-World Graphs
- The Power of Linear-Time Data Reduction for Maximum Matching
- Changing Bases: Multistage Optimization for Matroids and Matchings
- Randomized Rumor Spreading in Dynamic Graphs
- How to match when all vertices arrive online
- Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model
- Paths, Trees, and Flowers
- Parameterized Algorithms
- Computing maximum matchings in temporal graphs.
- Connectivity and inference problems for temporal networks
- Approximating multistage matching problems
- On the complexity of \(k\)-SAT
