A faster parameterized algorithm for temporal matching

DOI10.1016/J.IPL.2021.106181MaRDI QIDQ2059876zbMATH OpenOpenAlexFDO

Authors 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

\(\Delta\)-windowsgraph algorithmsparameterized algorithmstemporal graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Computing maximum matchings in temporal graphs.
• Computing maximum matchings in temporal graphs
• On the complexity of timed pattern matching
• Faster algorithms for semi-matching problems
• A Boyer-Moore type algorithm for timed pattern matching
• Fast algorithms for a class of temporal range queries.
• Maximum 0-1 timed matching on temporal graphs
• Faster algorithms for semi-matching problems (extended abstract)
• Sublinear-Time Parallel Algorithms for Matching and Related Problems
• Fast timing-based algorithms

Cites work

• Approximating multistage matching problems
• Changing bases: multistage optimization for matroids and matchings
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computing maximum matchings in temporal graphs.
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Finding temporal paths under waiting time constraints
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 3974318 (Why is no real title available?)
• scientific article; zbMATH DE number 7238962 (Why is no real title available?)
• Matching theory
• Multistage graph problems on a global budget
• Multistage Vertex Cover
• Parameterized Algorithms for Diverse Multistage Problems
• Reducibility among combinatorial problems
• Representative families for matroid intersections, with applications to location, packing, and covering problems
• Temporal matching
• Temporal matching on geometric graph data
• Temporal vertex cover with a sliding time window
• The complexity of finding small separators in temporal graphs

Cited in

(6)

• Fast SOLA-based time scale modification using envelope matching
• Computing maximum matchings in temporal graphs.
• On finding separators in temporal split and permutation graphs
• A recursive full search algorithm based on temporal correlation
• Computing maximum matchings in temporal graphs
• Parameterized algorithmics for time-evolving structures: temporalizing and multistaging

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

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