Computing maximum matchings in temporal graphs.

DOI10.4230/LIPICS.STACS.2020.27MaRDI QIDQ5874299zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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

Cited in

(18)

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