A faster parameterized algorithm for temporal matching

DOI10.1016/j.ipl.2021.106181OpenAlexW3192464375MaRDI QIDQ2059876

Philipp Zschoche

Publication date: 14 December 2021

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmsparameterized algorithmstemporal graphs\(\Delta\)-windows

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Computing maximum matchings in temporal graphs ⋮ On finding separators in temporal split and permutation graphs

Cites Work

• Fundamentals of parameterized complexity
• Multistage graph problems on a global budget
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Finding temporal paths under waiting time constraints
• The complexity of finding small separators in temporal graphs
• Temporal vertex cover with a sliding time window
• Representative families for matroid intersections, with applications to location, packing, and covering problems
• Temporal matching
• Temporal matching on geometric graph data
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Reducibility among Combinatorial Problems
• Changing Bases: Multistage Optimization for Matroids and Matchings
• Computing maximum matchings in temporal graphs.
• Multistage Vertex Cover
• Temporal graph classes: a view through temporal separators
• Approximating multistage matching problems
• Parameterized Algorithms for Diverse Multistage Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A faster parameterized algorithm for temporal matching