Cover Image

Monitoring graph edges via shortest paths: computational complexity and approximation algorithms

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Colli, Giordano
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On graphs coverable by k shortest paths
by: Dumas, Maël, et al.
Published: (2022)

Centrality of shortest paths: Algorithms and complexity results
by: Phosavanh, Johnson, et al.
Published: (2024)

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

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

Phase transition in the computational complexity of the shortest common superstring and genome assembly
by: Fernandez, L. A., et al.
Published: (2022)

Isometric path complexity of graphs
by: Chakraborty, Dibyayan, et al.
Published: (2022)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
by: Chakraborty, Dibyayan, et al.
Published: (2024)

On the approximability of graph visibility problems
by: Bilò, Davide, et al.
Published: (2024)

A new metric for evaluating the performance and complexity of computer programs: A new approach to the traditional ways of measuring the complexity of algorithms and estimating running times
by: Folea, Rares, et al.
Published: (2025)

On the power of counting the total number of computation paths of NPTMs
by: Bakali, Eleni, et al.
Published: (2023)

The complexity of computing in continuous time: space complexity is precision
by: Blanc, Manon, et al.
Published: (2024)

Complexity and algorithms for matching cut problems in graphs without long induced paths and cycles
by: Le, Hoang-Oanh, et al.
Published: (2023)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
by: Esmer, Barış Can, et al.
Published: (2022)

Algorithms and complexity for monitoring edge-geodetic sets in graphs
by: Foucaud, Florent, et al.
Published: (2024)

Quantum algorithms for path and cycle containment problems
by: Cornelissen, Arjan, et al.
Published: (2026)

Simple inexpensive vertex and edge invariants distinguishing dataset strongly regular graphs
by: Duda, Jarek
Published: (2024)

Unconventional complexity classes in unconventional computing (extended abstract)
by: Porreca, Antonio E.
Published: (2024)

On the complexity of embedding in graph products
by: Biedl, Therese, et al.
Published: (2023)

Faster algorithms for graph homomorphism via tractable constraint satisfaction
by: Carbonnel, Clément
Published: (2026)

Hunting a rabbit: complexity, approximability and some characterizations
by: Ben-Ameur, Walid, et al.
Published: (2025)

Is a LOCAL algorithm computable?
by: Cruciani, Antonio, et al.
Published: (2026)

Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems
by: Bender, Matías, et al.
Published: (2025)

Lower bounds for quantum-inspired classical algorithms via communication complexity
by: Mande, Nikhil S., et al.
Published: (2024)

Simple approximation algorithms for Polyamorous Scheduling
by: Biktairov, Yuriy, et al.
Published: (2024)

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
by: Cai, Jin-Yi, et al.
Published: (2024)

Quantum computational complexity of matrix functions
by: Cifuentes, Santiago, et al.
Published: (2024)

A $4/3$ ratio approximation algorithm for the Tree Augmentation Problem by deferred local-ratio and climbing
by: Kortsarz, Guy
Published: (2026)

On the complexity of unique quantum witnesses and quantum approximate counting
by: Anshu, Anurag, et al.
Published: (2024)

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
by: Dell, Holger, et al.
Published: (2022)

Physical complexity and black hole quantum computers
by: Reilly, Michele, et al.
Published: (2025)

Learning complexity of gradient descent and conjugate gradient algorithms
by: Jiao, Xianqi, et al.
Published: (2024)

A parameterized algorithm for $K_r$-factors in graphs of high minimum degree
by: Gan, Luyining, et al.
Published: (2023)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
by: Singer, Noah G.
Published: (2025)

On the complexity of computing Strahler numbers
by: Ganardi, Moses, et al.
Published: (2025)

On the complexity and approximability of Bounded access Lempel Ziv coding
by: Cicalese, Ferdinando, et al.
Published: (2024)

Reducing the complexity of computing the values of a Nash equilibrium
by: Chatterjee, Debtoru, et al.
Published: (2025)

A universal bound on the space complexity of Directed Acyclic Graph computations
by: Bilardi, Gianfranco, et al.
Published: (2024)

On the complex zeros and the computational complexity of approximating the reliability polynomial
by: Bencs, Ferenc, et al.
Published: (2025)

Polynomial kernels for edge modification problems towards block and strictly chordal graphs
by: Dumas, Maël, et al.
Published: (2022)

On a class of interdiction problems with partition matroids: complexity and polynomial-time algorithms
by: Ketkov, Sergey S., et al.
Published: (2024)