Buchumschlag

On girth and the parameterized complexity of token sliding and token jumping

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bartier, Valentin, Bousquet, Nicolas, Dallard, Clément, Lomer, Kyle, Mouawad, Amer E.
Format:	Preprint
Veröffentlicht:	2020
Schlagworte:	Computational Complexity Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Parameterized Shortest Path Reconfiguration
von: Bousquet, Nicolas, et al.
Veröffentlicht: (2024)

On the complexity of constrained reconfiguration and motion planning
von: Bousquet, Nicolas, et al.
Veröffentlicht: (2025)

Parameterized complexity of reconfiguration of atoms
von: Cooper, Alexandre, et al.
Veröffentlicht: (2021)

The tape reconfiguration problem and its consequences for dominating set reconfiguration
von: Bousquet, Nicolas, et al.
Veröffentlicht: (2025)

Kernelization Complexity of Solution Discovery Problems
von: Grobler, Mario, et al.
Veröffentlicht: (2024)

Induced Minor Models. II. Sufficient conditions for polynomial-time detection of induced minors
von: Dallard, Clément, et al.
Veröffentlicht: (2024)

On the parameterized complexity of Broadcast Independence and Broadcast Packing
von: Dumont, Joanne, et al.
Veröffentlicht: (2026)

Independent set reconfiguration in H-free graphs
von: Bartier, Valentin, et al.
Veröffentlicht: (2024)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
von: S., Karthik C., et al.
Veröffentlicht: (2023)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
von: Kim, Eun Jung, et al.
Veröffentlicht: (2022)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

The parameterized complexity of Strong Conflict-Free Vertex-Connection Colorability
von: Feghali, Carl, et al.
Veröffentlicht: (2025)

On Algorithmic Meta-Theorems for Solution Discovery: Tractability and Barriers
von: Bousquet, Nicolas, et al.
Veröffentlicht: (2025)

The communication complexity of distributed estimation
von: Gopalan, Parikshit, et al.
Veröffentlicht: (2025)

On the complexity and approximability of Bounded access Lempel Ziv coding
von: Cicalese, Ferdinando, et al.
Veröffentlicht: (2024)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
von: Enright, Jessica, et al.
Veröffentlicht: (2020)

The complexity of testing all properties of planar graphs, and the role of isomorphism
von: Basu, Sabyasachi, et al.
Veröffentlicht: (2021)

Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
von: Michel, Lukas, et al.
Veröffentlicht: (2023)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
von: Yang, Yang
Veröffentlicht: (2024)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
von: Esmer, Barış Can, et al.
Veröffentlicht: (2022)

Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension
von: Bartier, Valentin, et al.
Veröffentlicht: (2023)

Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
von: Maalouly, Nicolas El, et al.
Veröffentlicht: (2025)

On the complexity of global Roman domination problem in graphs
von: Reddy, Sangam Balchandar, et al.
Veröffentlicht: (2026)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
von: Li, Tiange, et al.
Veröffentlicht: (2026)

A Note on Fine-Grained Quantum Reductions for Linear Algebraic Problems
von: Doney, Kyle, et al.
Veröffentlicht: (2025)

Improving Merge Sort and Quick Sort Performance by Utilizing Alphadev's Sorting Networks as Base Cases
von: Aly, Anas Gamal, et al.
Veröffentlicht: (2025)

On Detecting $H$-Induced Minors for Small $H$
von: Eagling-Vose, Tala, et al.
Veröffentlicht: (2026)

Uniformity testing when you have the source code
von: Canonne, Clément L., et al.
Veröffentlicht: (2024)

On the complexity of symmetric vs. functional PCSPs
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2022)

Centrality of shortest paths: Algorithms and complexity results
von: Phosavanh, Johnson, et al.
Veröffentlicht: (2024)

The Sample Complexity of Replicable Realizable PAC Learning
von: Larsen, Kasper Green, et al.
Veröffentlicht: (2026)

Improved Algorithm for Permutation Testing
von: Zhang, Xiaojin
Veröffentlicht: (2020)

On the Mysteries of MAX NAE-SAT
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2020)

Removable Online Knapsack and Advice
von: Böckenhauer, Hans-Joachim, et al.
Veröffentlicht: (2020)

The Query Complexity of Local Search and Brouwer in Rounds
von: Brânzei, Simina, et al.
Veröffentlicht: (2020)

Neighborhood-Aware Graph Labeling Problem
von: Shahverdikondori, Mohammad, et al.
Veröffentlicht: (2026)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2025)

Lazy Kronecker Product
von: Song, Zhao
Veröffentlicht: (2026)

The Trichotomy of Regular Property Testing
von: Bathie, Gabriel, et al.
Veröffentlicht: (2025)

Complexity of Local Search for Euclidean Clustering Problems
von: Manthey, Bodo, et al.
Veröffentlicht: (2023)