Computing maximum matchings in temporal graphs.

DOI10.4230/LIPICS.STACS.2020.27OpenAlexW2998856043MaRDI QIDQ5874299FDOQ5874299

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

Publication date: 7 February 2023

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

Recommendations

• Maximum 0-1 timed matching on temporal graphs
• 0-1 timed matching in bipartite temporal graphs
• A faster parameterized algorithm for temporal matching
• Temporal matching
• Temporal vertex cover with a sliding time window

zbMATH Keywords

approximation algorithmAPX-hardnessfixed-parameter tractabilityindependent setNP-hardnesstemporal graphlink streamtemporal line graph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited In (18)

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

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

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