Cover Image

Knapsack: Connectedness, Path, and Shortest-Path

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dey, Palash, Kolay, Sudeshna, Singh, Sipra
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms Artificial Intelligence
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Knapsack with Vertex Cover, Set Cover, and Hitting Set
by: Dey, Palash, et al.
Published: (2024)

Knapsack on Graphs with Relaxed Neighborhood Constraints
by: Dey, Palash, et al.
Published: (2025)

Dominating Set Knapsack: Profit Optimization on Dominating Sets
by: Singh, Sipra
Published: (2025)

Enhanced Methods for the Weight Constrained Shortest Path Problem
by: Ahmadi, Saman, et al.
Published: (2022)

Minimizing Envy and Maximizing Happiness in Graphical House Allocation
by: Dhar, Anubhav, et al.
Published: (2025)

Tightest Admissible Shortest Path
by: Weiss, Eyal, et al.
Published: (2023)

Recognizing and Eliciting Weakly Single Crossing Profiles on Trees
by: Dey, Palash
Published: (2016)

Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
by: Dey, Palash, et al.
Published: (2026)

A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates
by: Weiss, Eyal, et al.
Published: (2022)

Query Complexity of Tournament Solutions
by: Maiti, Arnab, et al.
Published: (2016)

The Discrepancy of Shortest Paths
by: Bodwin, Greg, et al.
Published: (2024)

On Constrained and k Shortest Paths
by: Bendahi, Abderrahim, et al.
Published: (2024)

Shortest Paths in Multimode Graphs
by: Kirkpatrick, Yael, et al.
Published: (2025)

All-Hops Shortest Paths
by: Williams, Virginia Vassilevska, et al.
Published: (2024)

The Steiner Shortest Path Tree Problem
by: Asher, Omer, et al.
Published: (2025)

Verifying Shortest Paths in Linear Time
by: Shokry, Ahmed, et al.
Published: (2024)

Hierarchical Multicriteria Shortest Path Search
by: Kurbanov, Temirlan, et al.
Published: (2025)

Covering Approximate Shortest Paths with DAGs
by: Assadi, Sepehr, et al.
Published: (2025)

Shortcutting for Negative-Weight Shortest Path
by: Li, George Z., et al.
Published: (2025)

Fully Dynamic Shortest Paths in Sparse Digraphs
by: Karczmarz, Adam, et al.
Published: (2024)

Hardness of Approximation for Shortest Path with Vector Costs
by: Carlson, Charlie, et al.
Published: (2025)

Parameterized Complexity of Finding Dissimilar Shortest Paths
by: Funayama, Ryo, et al.
Published: (2024)

On Incremental Approximate Shortest Paths in Directed Graphs
by: Górkiewicz, Adam, et al.
Published: (2025)

Breaking the Bellman-Ford Shortest-Path Bound
by: Elmasry, Amr
Published: (2024)

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
by: Banik, Aritra, et al.
Published: (2025)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
by: Haeupler, Bernhard, et al.
Published: (2025)

Deterministic Padded Decompositions and Negative-Weight Shortest Paths
by: Li, Jason
Published: (2025)

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
by: Pilipczuk, Michał, et al.
Published: (2025)

Evolving A* to Efficiently Solve the k Shortest-Path Problem (Extended Version)
by: López, Carlos Linares, et al.
Published: (2024)

On Computing Top-$k$ Simple Shortest Paths from a Single Source
by: D'Emidio, Mattia, et al.
Published: (2025)

Incremental Approximate Single-Source Shortest Paths with Predictions
by: McCauley, Samuel, et al.
Published: (2025)

Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity
by: Pham, Canh V.
Published: (2024)

Predictive Spike Timing Enables Distributed Shortest Path Computation in Spiking Neural Networks
by: Storesund, Simen, et al.
Published: (2025)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
by: Dory, Michal, et al.
Published: (2022)

Improved 2-Approximate Shortest Paths for close vertex pairs
by: Gupta, Manoj
Published: (2025)

All-Pairs Shortest Paths with Few Weights per Node
by: Abboud, Amir, et al.
Published: (2025)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
by: Ashvinkumar, Vikrant, et al.
Published: (2024)

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

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
by: Chitnis, Rajesh, et al.
Published: (2024)

Uniform Sampling of Negative Edge Weights in Shortest Path Networks
by: Geis, Lukas, et al.
Published: (2024)