Image de couverture de livre

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Bilò, Davide, Colli, Giordano, Forlizzi, Luca, Leucci, Stefano
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
par: Bilò, Davide, et autres
Publié: (2024)

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
par: Tale, Prafullkumar
Publié: (2025)

Metric Dimension and Geodetic Set Parameterized by Vertex Cover
par: Foucaud, Florent, et autres
Publié: (2024)

Graph Spanners for Group Steiner Distances
par: Bilò, Davide, et autres
Publié: (2024)

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set
par: Chu, Huairui, et autres
Publié: (2023)

Temporal queries for dynamic temporal forests
par: Bilò, Davide, et autres
Publié: (2024)

On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem
par: Bhaskar, Umang, et autres
Publié: (2025)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
par: Adriaens, Florian, et autres
Publié: (2024)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
par: Herrmann, Anton, et autres
Publié: (2025)

A Complexity Analysis of the c-Closed Vertex Deletion Problem
par: Lehner, Lisa, et autres
Publié: (2025)

Self-referential instances of the dominating set problem are irreducible
par: Zhou, Guangyan
Publié: (2026)

Dominating Set Knapsack: Profit Optimization on Dominating Sets
par: Singh, Sipra
Publié: (2025)

Knapsack with Vertex Cover, Set Cover, and Hitting Set
par: Dey, Palash, et autres
Publié: (2024)

On Approximating the Dynamic and Discrete Network Flow Problem
par: Manna, Bubai, et autres
Publié: (2024)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
par: Esmer, Barış Can, et autres
Publié: (2022)

Testing Properties of Edge Distributions
par: Fei, Yumou
Publié: (2026)

Maximization of Approximately Submodular Functions
par: Horel, Thibaut, et autres
Publié: (2024)

Matching and Edge Cover in Temporal Graphs
par: Cioni, Lapo, et autres
Publié: (2025)

Improved Hardness-of-Approximation for Token Swapping
par: Hiken, Sam, et autres
Publié: (2024)

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
par: Hirahara, Shuichi, et autres
Publié: (2024)

Rounding Large Independent Sets on Expanders
par: Bafna, Mitali, et autres
Publié: (2024)

Hardness and Tractability of T_{h+1}-Free Edge Deletion
par: Gaikwad, Ajinkya, et autres
Publié: (2026)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
par: Putterman, Aaron, et autres
Publié: (2026)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
par: Gadekar, Ameet, et autres
Publié: (2025)

On the Hardness of Approximation of the Fair k-Center Problem
par: Thejaswi, Suhas
Publié: (2026)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
par: Wang, Yichuan
Publié: (2024)

Linear Space Streaming Lower Bounds for Approximating CSPs
par: Chou, Chi-Ning, et autres
Publié: (2021)

A Note on Approximability of Densest At-Least-k-Subgraph
par: Laekhanukit, Bundit, et autres
Publié: (2026)

Deterministic Independent Sets in the Semi-Streaming Model
par: Ye, Daniel
Publié: (2025)

Parameterized Max Min Feedback Vertex Set
par: Lampis, Michael, et autres
Publié: (2023)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
par: Moroie, Gregory
Publié: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
par: Singer, Noah G., et autres
Publié: (2026)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
par: Assadi, Sepehr, et autres
Publié: (2024)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
par: Grossman, Ofer, et autres
Publié: (2023)

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
par: Bringmann, Karl, et autres
Publié: (2024)

Scheduling Problems with Constrained Rejections
par: Davies, Sami, et autres
Publié: (2025)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
par: Buhrman, Harry, et autres
Publié: (2025)

String Consensus Problems with Swaps and Substitutions
par: Gabory, Estéban, et autres
Publié: (2025)

Equivalent Instances for Scheduling and Packing Problems
par: Jansen, Klaus, et autres
Publié: (2025)

Pseudodeterministic Algorithms for Minimum Cut Problems
par: Agarwala, Aryan, et autres
Publié: (2025)