Copertina

Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bonnet, Édouard, Geniet, Colin, Kim, Eun Jung, Moon, Sungmin
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms Discrete Mathematics Combinatorics 68Q25 F.2.2
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Coloring Hardness on Low Twin-Width Graphs
di: Bonnet, Édouard
Pubblicazione: (2025)

Answering Related Questions
di: Bonnet, Édouard
Pubblicazione: (2025)

Treewidth Inapproximability and Tight ETH Lower Bound
di: Bonnet, Édouard
Pubblicazione: (2024)

Interval Graphs are Reconstructible
di: Heinrich, Irene, et al.
Pubblicazione: (2025)

Mim-Width is paraNP-complete
di: Bergougnoux, Benjamin, et al.
Pubblicazione: (2025)

Induced Disjoint Paths Without an Induced Minor
di: Aboulker, Pierre, et al.
Pubblicazione: (2025)

A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm
di: Hougardy, Stefan, et al.
Pubblicazione: (2025)

Maximum Independent Set when excluding an induced minor: $K_1 + tK_2$ and $tC_3 \uplus C_4$
di: Bonnet, Édouard, et al.
Pubblicazione: (2023)

Maximum Matchings in Geometric Intersection Graphs
di: Bonnet, Édouard, et al.
Pubblicazione: (2019)

An $11/6$-Approximation Algorithm for Vertex Cover on String Graphs
di: Bonnet, Édouard, et al.
Pubblicazione: (2024)

Pliability and Approximating Max-CSPs
di: Romero, Miguel, et al.
Pubblicazione: (2019)

The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
di: Heimann, Sophia, et al.
Pubblicazione: (2024)

The Bottom-Left Algorithm for the Strip Packing Problem
di: Hougardy, Stefan, et al.
Pubblicazione: (2024)

Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
di: Bonnet, Édouard, et al.
Pubblicazione: (2023)

O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold
di: Bell, Tolson, et al.
Pubblicazione: (2024)

Sparse Induced Subgraphs of Large Treewidth
di: Bonnet, Édouard
Pubblicazione: (2024)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
di: Chen, Yijia, et al.
Pubblicazione: (2023)

A Constant Factor Approximation for Directed Feedback Vertex Set in Graphs of Bounded Genus
di: Sun, Hao
Pubblicazione: (2023)

On the Integrality Gap of Directed Steiner Tree LPs with Relatively Integral Solutions
di: Laekhanukit, Bundit
Pubblicazione: (2024)

A New Temporal Interpretation of Cluster Editing
di: Bocci, Cristiano, et al.
Pubblicazione: (2022)

Adjacency Labeling Schemes for Small Classes
di: Bonnet, Édouard, et al.
Pubblicazione: (2024)

Sublinear-Time Computation in the Presence of Online Erasures
di: Kalemaj, Iden, et al.
Pubblicazione: (2021)

On the Approximation Ratio of the $k$-Opt and Lin-Kernighan Algorithm
di: Zhong, Xianghui
Pubblicazione: (2019)

A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem
di: Heimann, Sophia, et al.
Pubblicazione: (2025)

Overlapping Biclustering
di: Bentert, Matthias, et al.
Pubblicazione: (2025)

Simple minimally unsatisfiable subsets of 2-CNFs
di: Kullmann, Oliver, et al.
Pubblicazione: (2026)

Moderately beyond clique-width: reduced component max-leaf and related parameters
di: Bonnet, Édouard, et al.
Pubblicazione: (2026)

Revisiting Chazelle's Implementation of the Bottom-Left Heuristic: A Corrected and Rigorous Analysis
di: Michel, Stefan
Pubblicazione: (2025)

Competitive Query Minimization for Stable Matching with One-Sided Uncertainty
di: Bampis, Evripidis, et al.
Pubblicazione: (2024)

Optimal non-adaptive algorithm for edge estimation
di: Bishnu, Arijit, et al.
Pubblicazione: (2025)

Searching in trees with monotonic query times
di: Dereniowski, Dariusz, et al.
Pubblicazione: (2024)

On the twin-width of near-regular graphs
di: Heinrich, Irene, et al.
Pubblicazione: (2025)

Symmetric-Difference (Degeneracy) and Signed Tree Models
di: Bonnet, Édouard, et al.
Pubblicazione: (2024)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
di: Levet, Michael, et al.
Pubblicazione: (2023)

Extending Exact Integrality Gap Computations for the Metric TSP
di: Cook, William, et al.
Pubblicazione: (2026)

On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem
di: Heimann, Sophia, et al.
Pubblicazione: (2026)

Graphs with no long claws: An improved bound for the analog of the Gyárfás' path argument
di: Bourneuf, Romain, et al.
Pubblicazione: (2025)

Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy
di: Feldman, Moran, et al.
Pubblicazione: (2026)

APTAS for bin packing with general cost structures
di: Jaykrishnan, G., et al.
Pubblicazione: (2024)

A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads
di: Rockel-Wolff, Benjamin
Pubblicazione: (2024)