Cover Image

Answering Related Questions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Bonnet, Édouard
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Complexity Discrete Mathematics Combinatorics 68Q25 F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Treewidth Inapproximability and Tight ETH Lower Bound
by: Bonnet, Édouard
Published: (2024)

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

Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications
by: Bonnet, Édouard, et al.
Published: (2026)

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

Interval Graphs are Reconstructible
by: Heinrich, Irene, et al.
Published: (2025)

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

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

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

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

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

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

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

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

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

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

A Decomposition Approach to the Weighted $k$-server Problem
by: Ayyadevara, Nikhil, et al.
Published: (2024)

Probabilistic Analysis of Edge Elimination for Euclidean TSP
by: Zhong, Xianghui
Published: (2018)

Color-Constrained Arborescences in Edge-Colored Digraphs
by: Ardra, P. S., et al.
Published: (2025)

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

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

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

Sparse Induced Subgraphs of Large Treewidth
by: Bonnet, Édouard
Published: (2024)

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

NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
by: Fairbairn, David L., et al.
Published: (2024)

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

On Solving Reachability in Grid Digraphs using a Psuedoseparator
by: Jain, Rahul, et al.
Published: (2019)

Computing parameters that generalize interval graphs using restricted modular partitions
by: Bonomo-Braberman, Flavia, et al.
Published: (2025)

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

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

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
by: Jansen, Klaus, et al.
Published: (2024)

Logarithmic Weisfeiler--Leman and Treewidth
by: Levet, Michael, et al.
Published: (2023)

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

Parallel Algorithms for Group Isomorphism via Code Equivalence
by: Levet, Michael
Published: (2026)

On weighted graph separation problems and flow-augmentation
by: Kim, Eun Jung, et al.
Published: (2022)

Continuous Flattening and Reversing of Convex Polyhedral Linkages
by: Demaine, Erik D., et al.
Published: (2024)

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

m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs
by: Calamoneri, Tiziana, et al.
Published: (2025)

The Minimum Eternal Vertex Cover Problem on a Subclass of Series-Parallel Graphs
by: Calamoneri, Tiziana, et al.
Published: (2025)

Scheduling with Time Dependent Utilities: Fairness and Efficiency
by: Nicosia, Gaia, et al.
Published: (2026)