Image de couverture de livre

Coloring Hardness on Low Twin-Width Graphs

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Bonnet, Édouard
Format:	Preprint
Publié:	2025
Sujets:	Computational Complexity Discrete Mathematics Data Structures and Algorithms Combinatorics 68Q25 F.2.2
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Answering Related Questions
par: Bonnet, Édouard
Publié: (2025)

Mim-Width is paraNP-complete
par: Bergougnoux, Benjamin, et autres
Publié: (2025)

Treewidth Inapproximability and Tight ETH Lower Bound
par: Bonnet, Édouard
Publié: (2024)

Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications
par: Bonnet, Édouard, et autres
Publié: (2026)

Induced Disjoint Paths Without an Induced Minor
par: Aboulker, Pierre, et autres
Publié: (2025)

Interval Graphs are Reconstructible
par: Heinrich, Irene, et autres
Publié: (2025)

A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm
par: Hougardy, Stefan, et autres
Publié: (2025)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
par: Chen, Yijia, et autres
Publié: (2023)

A New Temporal Interpretation of Cluster Editing
par: Bocci, Cristiano, et autres
Publié: (2022)

An $11/6$-Approximation Algorithm for Vertex Cover on String Graphs
par: Bonnet, Édouard, et autres
Publié: (2024)

Maximum Matchings in Geometric Intersection Graphs
par: Bonnet, Édouard, et autres
Publié: (2019)

Color-Constrained Arborescences in Edge-Colored Digraphs
par: Ardra, P. S., et autres
Publié: (2025)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
par: Levet, Michael, et autres
Publié: (2023)

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

Sublinear-Time Computation in the Presence of Online Erasures
par: Kalemaj, Iden, et autres
Publié: (2021)

Symmetric-Difference (Degeneracy) and Signed Tree Models
par: Bonnet, Édouard, et autres
Publié: (2024)

Pliability and Approximating Max-CSPs
par: Romero, Miguel, et autres
Publié: (2019)

A Decomposition Approach to the Weighted $k$-server Problem
par: Ayyadevara, Nikhil, et autres
Publié: (2024)

Probabilistic Analysis of Edge Elimination for Euclidean TSP
par: Zhong, Xianghui
Publié: (2018)

The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
par: Heimann, Sophia, et autres
Publié: (2024)

The Bottom-Left Algorithm for the Strip Packing Problem
par: Hougardy, Stefan, et autres
Publié: (2024)

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

Maximum Independent Set when excluding an induced minor: $K_1 + tK_2$ and $tC_3 \uplus C_4$
par: Bonnet, Édouard, et autres
Publié: (2023)

Sparse Induced Subgraphs of Large Treewidth
par: Bonnet, Édouard
Publié: (2024)

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

NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
par: Fairbairn, David L., et autres
Publié: (2024)

Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases
par: Meusel, Julia, et autres
Publié: (2025)

O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold
par: Bell, Tolson, et autres
Publié: (2024)

On Solving Reachability in Grid Digraphs using a Psuedoseparator
par: Jain, Rahul, et autres
Publié: (2019)

m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs
par: Calamoneri, Tiziana, et autres
Publié: (2025)

Computing parameters that generalize interval graphs using restricted modular partitions
par: Bonomo-Braberman, Flavia, et autres
Publié: (2025)

The Minimum Eternal Vertex Cover Problem on a Subclass of Series-Parallel Graphs
par: Calamoneri, Tiziana, et autres
Publié: (2025)

On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs
par: MacRury, Calum, et autres
Publié: (2022)

APTAS for bin packing with general cost structures
par: Jaykrishnan, G., et autres
Publié: (2024)

Arborescences and Shortest Path Trees when Colors Matter
par: Ardra, P. S., et autres
Publié: (2024)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths
par: Beisegel, Jesse, et autres
Publié: (2025)

Solving Problems on Generalized Convex Graphs via Mim-Width
par: Bonomo-Braberman, Flavia, et autres
Publié: (2020)

Searching in trees with monotonic query times
par: Dereniowski, Dariusz, et autres
Publié: (2024)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
par: Jansen, Klaus, et autres
Publié: (2024)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs
par: Beisegel, Jesse, et autres
Publié: (2025)