Imagen de Portada

Centrality of shortest paths: Algorithms and complexity results

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Phosavanh, Johnson, Matsypura, Dmytro
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms Computational Complexity Optimization and Control
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

A note on the complexity of the picker routing problem in multi-block warehouses and related problems
por: Prunet, Thibault, et al.
Publicado: (2023)

Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints
por: Chen, Shengminjie, et al.
Publicado: (2026)

Computational complexity of the recoverable robust shortest path problem in acyclic digraphs
por: Kasperski, Adam, et al.
Publicado: (2024)

Solving convex QPs with structured sparsity under indicator conditions
por: Bienstock, Daniel, et al.
Publicado: (2024)

A Control-Theoretic Perspective on Optimal High-Order Optimization
por: Lin, Tianyi, et al.
Publicado: (2019)

A Continuous-Time Perspective on Global Acceleration for Monotone Equation Problems
por: Lin, Tianyi, et al.
Publicado: (2022)

On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank
por: Kurpisz, Adam, et al.
Publicado: (2026)

Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting
por: Gribanov, Dmitry, et al.
Publicado: (2026)

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

Delta-modular ILP Problems of Bounded Codimension, Discrepancy, and Convolution (new version)
por: Cherniavskii, M., et al.
Publicado: (2024)

Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
por: Blanchard, Moise
Publicado: (2024)

Simultaneous Network Design with Restricted Link Usage
por: Kakimura, Naonori, et al.
Publicado: (2025)

Unifying Formal Explanations: A Complexity-Theoretic Perspective
por: Bassan, Shahaf, et al.
Publicado: (2026)

Semidefinite programming and linear equations vs. homomorphism problems
por: Ciardo, Lorenzo, et al.
Publicado: (2023)

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
por: Kunisky, Dmitriy, et al.
Publicado: (2022)

Efficient Convex Optimization Requires Superlinear Memory
por: Marsden, Annie, et al.
Publicado: (2022)

Efficient approximation schemes for scheduling on a stochastic number of machines
por: Epstein, Leah, et al.
Publicado: (2024)

A Θ(m^9) ternary minimum-cost network flow LP model of the Assignment Problem polytope with applications to hard combinatorial optimization problems
por: Diaby, Moustapha
Publicado: (2016)

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

Precoloring extension with demands on paths
por: Das, Arun Kumar, et al.
Publicado: (2025)

Min-Max Optimization Requires Exponentially Many Queries
por: Bernasconi, Martino, et al.
Publicado: (2026)

Isometric path complexity of graphs
por: Chakraborty, Dibyayan, et al.
Publicado: (2022)

On the complexity of the upgrading version of the maximal covering location problem
por: Baldomero-Naranjo, Marta, et al.
Publicado: (2024)

The communication complexity of distributed estimation
por: Gopalan, Parikshit, et al.
Publicado: (2025)

Parameterized complexity of reconfiguration of atoms
por: Cooper, Alexandre, et al.
Publicado: (2021)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
por: Kluk, Kacper, et al.
Publicado: (2025)

An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies
por: Chen, Yike, et al.
Publicado: (2024)

Deriving the Gradients of Some Popular Optimal Transport Algorithms
por: Xie, Fangzhou
Publicado: (2025)

Branch-and-Bound Algorithms as Polynomial-time Approximation Schemes
por: Encz, Koppány István, et al.
Publicado: (2025)

Solving Linear Programs with Fast Online Learning Algorithms
por: Gao, Wenzhi, et al.
Publicado: (2021)

Two-sided Assortment Optimization: Adaptivity Gaps and Approximation Algorithms
por: Housni, Omar El, et al.
Publicado: (2024)

(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs
por: Hunkenschröder, Christoph, et al.
Publicado: (2025)

An Efficient Algorithm for Minimizing Ordered Norms in Fractional Load Balancing
por: Blankenburg, Daniel, et al.
Publicado: (2025)

A Variational-Calculus Approach to Online Algorithm Design and Analysis
por: Xu, Pan
Publicado: (2025)

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

On girth and the parameterized complexity of token sliding and token jumping
por: Bartier, Valentin, et al.
Publicado: (2020)

Efficient Catalytic Graph Algorithms
por: Cook, James, et al.
Publicado: (2025)

Improved Algorithm for Permutation Testing
por: Zhang, Xiaojin
Publicado: (2020)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
por: Enright, Jessica, et al.
Publicado: (2020)

The complexity of testing all properties of planar graphs, and the role of isomorphism
por: Basu, Sabyasachi, et al.
Publicado: (2021)