Cover Image

Matching and Edge Cover in Temporal Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cioni, Lapo, Dondi, Riccardo, Marino, Andrea, Schoeters, Jason, Silva, Ana
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Novel Complexity Results for Temporal Separators with Deadlines
by: Dondi, Riccardo, et al.
Published: (2025)

Vector TSP: A Traveling Salesperson Problem with Racetrack-like Acceleration Constraints
by: Casteigts, Arnaud, et al.
Published: (2020)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
by: Herrmann, Anton, et al.
Published: (2025)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
by: Putterman, Aaron, et al.
Published: (2026)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
by: Assadi, Sepehr, et al.
Published: (2024)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
by: Maalouly, Nicolas El, et al.
Published: (2025)

Knapsack with Vertex Cover, Set Cover, and Hitting Set
by: Dey, Palash, et al.
Published: (2024)

Testing Properties of Edge Distributions
by: Fei, Yumou
Published: (2026)

Bipartite Matching is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)

Structural Parameterizations for Induced and Acyclic Matching
by: Lampis, Michael, et al.
Published: (2025)

The Fine-Grained Complexity of Episode Matching
by: Bille, Philip, et al.
Published: (2021)

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
by: Bilò, Davide, et al.
Published: (2025)

Parameterized Capacitated Vertex Cover Revisited
by: Lampis, Michael, et al.
Published: (2026)

Hardness and Tractability of T_{h+1}-Free Edge Deletion
by: Gaikwad, Ajinkya, et al.
Published: (2026)

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
by: Bilò, Davide, et al.
Published: (2024)

Parameterized Restless Temporal Path
by: Cauvi, Justine, et al.
Published: (2025)

Low-Sensitivity Matching via Sampling from Gibbs Distributions
by: Yoshida, Yuichi, et al.
Published: (2025)

Exact Algorithms for Distance to Unique Vertex Cover
by: Fioravantes, Foivos, et al.
Published: (2025)

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
by: Clinch, Katie, et al.
Published: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
by: Moroie, Gregory
Published: (2025)

Covering a Polyomino-Shaped Stain with Non-Overlapping Identical Stickers
by: Oka, Keigo, et al.
Published: (2026)

End Cover for Initial Value Problem: Complete Validated Algorithms with Complexity Analysis
by: Zhang, Bingwei, et al.
Published: (2026)

Forest Covers and Bounded Forest Covers
by: Gaur, Daya Ram, et al.
Published: (2024)

The Complexity of Transitively Orienting Temporal Graphs
by: Mertzios, George B., et al.
Published: (2021)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
by: Döring, Simon, et al.
Published: (2024)

The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching
by: Dreier, Jan, et al.
Published: (2026)

Efficient Catalytic Graph Algorithms
by: Cook, James, et al.
Published: (2025)

Knapsack on Graphs with Relaxed Neighborhood Constraints
by: Dey, Palash, et al.
Published: (2025)

The Parameterized Landscape of Labeled Graph Contractions
by: Lafond, Manuel, et al.
Published: (2025)

Neighborhood-Aware Graph Labeling Problem
by: Shahverdikondori, Mohammad, et al.
Published: (2026)

Residue Domination in Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2024)

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set
by: Chu, Huairui, et al.
Published: (2023)

Semi-Streaming Algorithms for Graph Property Certification
by: Das, Avinandan, et al.
Published: (2025)

Generalized Graph Packing Problems Parameterized by Treewidth
by: Esmer, Barış Can, et al.
Published: (2025)

Coloring Graphs with Few Colors in the Streaming Model
by: Assadi, Sepehr, et al.
Published: (2025)

Streaming Complexity Separations for Dense and Sparse Graphs
by: Liu, Yang P., et al.
Published: (2026)

Parameterized Algorithms for Editing to Uniform Cluster Graph
by: Gaikwad, Ajinkya, et al.
Published: (2024)

Colouring $(P_r+P_s)$-Free Graphs
by: Klimošová, Tereza, et al.
Published: (2018)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
by: Chudigiewitsch, Florian, et al.
Published: (2026)