Computing maximum matchings in temporal graphs.

DOI10.4230/LIPIcs.STACS.2020.27OpenAlexW2998856043MaRDI QIDQ5874299

Hendrik Molter, Victor Zamaraev, Rolf Niedermeier, Philipp Zschoche, George B. Mertzios

Publication date: 7 February 2023

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

zbMATH Keywords

approximation algorithmindependent setNP-hardnessfixed-parameter tractabilityAPX-hardnesstemporal graphlink streamtemporal line graph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (15)

As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Multistage graph problems on a global budget ⋮ Maximum 0-1 timed matching on temporal graphs ⋮ A new temporal interpretation of cluster editing ⋮ Temporal interval cliques and independent sets ⋮ Sharp Thresholds in Random Simple Temporal Graphs ⋮ Disentangling the computational complexity of network untangling ⋮ Computing maximum matchings in temporal graphs ⋮ Temporal matching on geometric graph data ⋮ Parameterised temporal exploration problems ⋮ Temporal cliques admit sparse spanners ⋮ Approximating multistage matching problems ⋮ Approximating multistage matching problems ⋮ Edge exploration of temporal graphs ⋮ A faster parameterized algorithm for temporal matching

This page was built for publication: Computing maximum matchings in temporal graphs.