Cover Image

The Complexity of Temporal Vertex Cover in Small-Degree Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hamm, Thekla, Klobas, Nina, Mertzios, George B., Spirakis, Paul G.
Format:	Preprint
Published:	2022
Subjects:	Data Structures and Algorithms Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Temporal Graph Realization With Bounded Stretch
by: Mertzios, George B., et al.
Published: (2025)

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

A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs
by: Hamm, Thekla, et al.
Published: (2026)

Parameterized Local Search for Vertex Cover: When only the Search Radius is Crucial
by: Komusiewicz, Christian, et al.
Published: (2026)

Eternal Vertex Cover on Bipartite and Co-Bipartite Graphs
by: Misra, Neeldhara, et al.
Published: (2022)

Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
by: German, Samuel
Published: (2026)

FO and MSO Model Checking on Temporal Graphs
by: Döring, Michelle, et al.
Published: (2026)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
by: Deligkas, Argyrios, et al.
Published: (2025)

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

Treewidth Parameterized by Feedback Vertex Number
by: Molter, Hendrik, et al.
Published: (2025)

Cutwidth Bounds via Vertex Partitions
by: Amarilli, Antoine, et al.
Published: (2025)

Computing Subset Vertex Covers in $H$-Free Graphs
by: Brettell, Nick, et al.
Published: (2023)

The Complexity of Cluster Vertex Splitting and Company
by: Firbas, Alexander, et al.
Published: (2023)

Metric Dimension and Geodetic Set Parameterized by Vertex Cover
by: Foucaud, Florent, et al.
Published: (2024)

Feedback Vertex Set for pseudo-disk graphs in subexponential FPT time
by: Berthe, Gaétan, et al.
Published: (2024)

The Parameterized Complexity of Vertex-Coloring Edge-Weighting
by: Aute, Shubhada, et al.
Published: (2026)

Approximate Realizations for Outerplanaric Degree Sequences
by: Bar-Noy, Amotz, et al.
Published: (2024)

A Faster Isomorphism Test for Graphs of Small Degree
by: Grohe, Martin, et al.
Published: (2018)

How to Reduce Temporal Cliques to Find Sparse Spanners
by: Angrick, Sebastian, et al.
Published: (2024)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
by: Paul-Pena, Daniel, et al.
Published: (2024)

Algorithmic Results for Weak Roman Domination Problem in Graphs
by: Paul, Kaustav, et al.
Published: (2024)

Extending Ghouila-Houri's Characterization of Comparability Graphs to Temporal Graphs
by: Charbit, Pierre, et al.
Published: (2025)

A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
by: Paul-Pena, Daniel, et al.
Published: (2022)

Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
by: Neuen, Daniel
Published: (2020)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
by: Foucaud, Florent, et al.
Published: (2023)

On Stable Cutsets in General and Minimum Degree Constrained Graphs
by: Vroon, Mats, et al.
Published: (2025)

Matrix Scaling: a New Heuristic for the Feedback Vertex Set Problem
by: Shook, James M., et al.
Published: (2025)

A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST
by: Jana, Satyabrata, et al.
Published: (2025)

Algorithmic Aspects of Temporal Betweenness
by: Buß, Sebastian, et al.
Published: (2020)

Isomorphism for Tournaments of Small Twin Width
by: Grohe, Martin, et al.
Published: (2023)

Minimum Sum Set Cover: Structures and Algorithm
by: Zhang, Zhongyi, et al.
Published: (2026)

Edge Clique Partition and Cover Beyond Independence
by: Fomin, Fedor V., et al.
Published: (2025)

Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
by: Fomin, Fedor V., et al.
Published: (2024)

Reweighted Spectral Partitioning Works: A Simple Algorithm for Vertex Separators in Special Graph Classes
by: Spalding-Jamieson, Jack
Published: (2025)

Online Graph Coloring for $k$-Colorable Graphs
by: Kawarabayashi, Ken-ichi, et al.
Published: (2025)

Parameterized Complexity of Path Set Packing
by: Aravind, N. R., et al.
Published: (2022)

The Complexity of Diameter on H-free graphs
by: Oostveen, Jelle J., et al.
Published: (2024)

Terminal Steiner tree problem : Complexity and Algorithms
by: S, Jyothish, et al.
Published: (2026)

Parameterized Complexity of Submodular Minimization under Uncertainty
by: Kakimura, Naonori, et al.
Published: (2024)

Stability in Graphs with Matroid Constraints
by: Fomin, Fedor V., et al.
Published: (2024)