Maximum 0-1 timed matching on temporal graphs
From MaRDI portal
Publication:2161255
DOI10.1016/j.dam.2021.12.027zbMath1494.05101arXiv2012.08909OpenAlexW4210685215WikidataQ114191470 ScholiaQ114191470MaRDI QIDQ2161255
Arobinda Gupta, Subhrangsu Mandal
Publication date: 4 August 2022
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2012.08909
Small world graphs, complex networks (graph-theoretic aspects) (05C82) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Traveling salesman problems in temporal graphs
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- 0-1 timed matching in bipartite temporal graphs
- Matching is as easy as matrix inversion
- On approximation properties of the independent set problem for low degree graphs
- A \(0(| V | \cdot | E |)\) algorithm for maximum matching of graphs
- Finding temporal paths under waiting time constraints
- The complexity of finding small separators in temporal graphs
- Temporal matching
- Maximum matchings in planar graphs via Gaussian elimination
- Complexity results for rainbow matchings
- Packing trees into planar graphs
- Efficient Graph Packing via Game Colouring
- A Problem Kernelization for Graph Packing
- A new algorithm for the assignment problem
- Network Flow and Testing Graph Connectivity
- Randomized $\tilde{O}(M(|V|))$ Algorithms for Problems in Matching Theory
- Shortest path with time constraints on movement and parking
- Convergecast Tree on Temporal Graphs
- Temporal Cliques Admit Sparse Spanners
- Changing Bases: Multistage Optimization for Matroids and Matchings
- Paths, Trees, and Flowers
- Algorithms – ESA 2004
- COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
- Computing maximum matchings in temporal graphs.
