New Approximations for Temporal Vertex Cover on Always Star Temporal Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Heck, Sophia, Akrida, Eleni
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Exploration of Always $S$-Connected Temporal Graphs
by: Adamson, Duncan, et al.
Published: (2026)

Temporal Graph Reconfiguration for Always-Connected Graphs
by: Sievers, Paul, et al.
Published: (2025)

The Complexity of Temporal Vertex Cover in Small-Degree Graphs
by: Hamm, Thekla, et al.
Published: (2022)

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

Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition
by: Davies-Peck, Peter
Published: (2026)

Approximately: Independence Implies Vertex Cover
by: Har-Peled, Sariel
Published: (2023)

Enumeration kernels for Vertex Cover and Feedback Vertex Set
by: Bougeret, Marin, et al.
Published: (2025)

An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers
by: Kobayashi, Yusuke, et al.
Published: (2026)

Matching and Edge Cover in Temporal Graphs
by: Cioni, Lapo, et al.
Published: (2025)

A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph
by: Kolmogorov, Vladimir, et al.
Published: (2026)

Capacitated Partition Vertex Cover and Partition Edge Cover
by: Dabas, Rajni, et al.
Published: (2025)

An Optimal Algorithm for Stochastic Vertex Cover
by: Brand, Jan van den, et al.
Published: (2026)

Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs
by: Cai, Xinwei, et al.
Published: (2023)

Weighted Partition Vertex and Edge Cover
by: Dabas, Rajni, et al.
Published: (2025)

Addressing Bias in Algorithmic Solutions: Exploring Vertex Cover and Feedback Vertex Set
by: Akhtar, Sheikh Shakil, et al.
Published: (2025)

New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications
by: Ding, Xiangyun, et al.
Published: (2025)

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
by: Saito, Rin, et al.
Published: (2025)

Parameterized Algorithms for Minimum Sum Vertex Cover
by: Aute, Shubhada, et al.
Published: (2024)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
by: Bentert, Matthias, et al.
Published: (2025)

Minimum Temporal Spanners in Happy Graphs
by: Casteigts, Arnaud, et al.
Published: (2026)

Beer Path Problems in Temporal Graphs
by: D'Ascenzo, Andrea, et al.
Published: (2025)

Diameter Shortcut Sets on Temporal Graphs
by: Quantmeyer, Gerome
Published: (2025)

Exploring Word-Representable Temporal Graphs
by: Adamson, Duncan
Published: (2025)

Cluster Vertex Deletion on Chordal Graphs
by: Cao, Yixin, et al.
Published: (2026)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Optimizing Distances for Multi-Broadcast in Temporal Graphs
by: Carnevale, Daniele, et al.
Published: (2026)

Exploring Temporal Graphs with Frequent and Regular Edges
by: Adamson, Duncan
Published: (2025)

9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity
by: Çivril, Ali
Published: (2024)

TGLib: An Open-Source Library for Temporal Graph Analysis
by: Oettershagen, Lutz, et al.
Published: (2022)

Maintaining Bipartite Colourings on Temporal Graphs on a Budget
by: Adamson, Duncan, et al.
Published: (2025)

Realization of Temporally Connected Graphs Based on Degree Sequences
by: Casteigts, Arnaud, et al.
Published: (2025)

Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous
by: Dogeas, Konstantinos, et al.
Published: (2023)

Quick-Sort Style Approximation Algorithms for Generalizations of Feedback Vertex Set in Tournaments
by: Gupta, Sushmita, et al.
Published: (2024)

Path-Reporting Distance Oracles for Vertex-Labeled Graphs
by: Neiman, Ofer, et al.
Published: (2026)

The Connected k-Vertex One-Center Problem on Graphs
by: Zhang, Jingru
Published: (2024)

Approximating Optimal Labelings for Temporal Connectivity
by: Carnevale, Daniele, et al.
Published: (2025)

Minimizing Reachability Times on Temporal Graphs via Shifting Labels
by: Deligkas, Argyrios, et al.
Published: (2021)

Approximating $δ$-Covering
by: Hartmann, Tim A., et al.
Published: (2024)

New Oracles and Labeling Schemes for Vertex Cut Queries
by: Jiang, Yonggang, et al.
Published: (2025)

Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems
by: Esmer, Barış Can, et al.
Published: (2024)