On girth and the parameterized complexity of token sliding and token jumping
Fuente:
arXiv
Salvato in:
| Autori principali: | Bartier, Valentin, Bousquet, Nicolas, Dallard, Clément, Lomer, Kyle, Mouawad, Amer E. |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
Documenti analoghi
Parameterized Shortest Path Reconfiguration
di: Bousquet, Nicolas, et al.
Pubblicazione: (2024)
di: Bousquet, Nicolas, et al.
Pubblicazione: (2024)
On the complexity of constrained reconfiguration and motion planning
di: Bousquet, Nicolas, et al.
Pubblicazione: (2025)
di: Bousquet, Nicolas, et al.
Pubblicazione: (2025)
Parameterized complexity of reconfiguration of atoms
di: Cooper, Alexandre, et al.
Pubblicazione: (2021)
di: Cooper, Alexandre, et al.
Pubblicazione: (2021)
The tape reconfiguration problem and its consequences for dominating set reconfiguration
di: Bousquet, Nicolas, et al.
Pubblicazione: (2025)
di: Bousquet, Nicolas, et al.
Pubblicazione: (2025)
Kernelization Complexity of Solution Discovery Problems
di: Grobler, Mario, et al.
Pubblicazione: (2024)
di: Grobler, Mario, et al.
Pubblicazione: (2024)
Induced Minor Models. II. Sufficient conditions for polynomial-time detection of induced minors
di: Dallard, Clément, et al.
Pubblicazione: (2024)
di: Dallard, Clément, et al.
Pubblicazione: (2024)
On the parameterized complexity of Broadcast Independence and Broadcast Packing
di: Dumont, Joanne, et al.
Pubblicazione: (2026)
di: Dumont, Joanne, et al.
Pubblicazione: (2026)
Independent set reconfiguration in H-free graphs
di: Bartier, Valentin, et al.
Pubblicazione: (2024)
di: Bartier, Valentin, et al.
Pubblicazione: (2024)
Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
di: S., Karthik C., et al.
Pubblicazione: (2023)
di: S., Karthik C., et al.
Pubblicazione: (2023)
Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
di: Kim, Eun Jung, et al.
Pubblicazione: (2022)
di: Kim, Eun Jung, et al.
Pubblicazione: (2022)
Self-referential instances of the dominating set problem are irreducible
di: Zhou, Guangyan
Pubblicazione: (2026)
di: Zhou, Guangyan
Pubblicazione: (2026)
The parameterized complexity of Strong Conflict-Free Vertex-Connection Colorability
di: Feghali, Carl, et al.
Pubblicazione: (2025)
di: Feghali, Carl, et al.
Pubblicazione: (2025)
On Algorithmic Meta-Theorems for Solution Discovery: Tractability and Barriers
di: Bousquet, Nicolas, et al.
Pubblicazione: (2025)
di: Bousquet, Nicolas, et al.
Pubblicazione: (2025)
The communication complexity of distributed estimation
di: Gopalan, Parikshit, et al.
Pubblicazione: (2025)
di: Gopalan, Parikshit, et al.
Pubblicazione: (2025)
On the complexity and approximability of Bounded access Lempel Ziv coding
di: Cicalese, Ferdinando, et al.
Pubblicazione: (2024)
di: Cicalese, Ferdinando, et al.
Pubblicazione: (2024)
The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
di: Enright, Jessica, et al.
Pubblicazione: (2020)
di: Enright, Jessica, et al.
Pubblicazione: (2020)
The complexity of testing all properties of planar graphs, and the role of isomorphism
di: Basu, Sabyasachi, et al.
Pubblicazione: (2021)
di: Basu, Sabyasachi, et al.
Pubblicazione: (2021)
Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
di: Michel, Lukas, et al.
Pubblicazione: (2023)
di: Michel, Lukas, et al.
Pubblicazione: (2023)
A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
di: Yang, Yang
Pubblicazione: (2024)
di: Yang, Yang
Pubblicazione: (2024)
List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
di: Esmer, Barış Can, et al.
Pubblicazione: (2022)
di: Esmer, Barış Can, et al.
Pubblicazione: (2022)
Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension
di: Bartier, Valentin, et al.
Pubblicazione: (2023)
di: Bartier, Valentin, et al.
Pubblicazione: (2023)
Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
di: Maalouly, Nicolas El, et al.
Pubblicazione: (2025)
di: Maalouly, Nicolas El, et al.
Pubblicazione: (2025)
On the complexity of global Roman domination problem in graphs
di: Reddy, Sangam Balchandar, et al.
Pubblicazione: (2026)
di: Reddy, Sangam Balchandar, et al.
Pubblicazione: (2026)
On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
di: Li, Tiange, et al.
Pubblicazione: (2026)
di: Li, Tiange, et al.
Pubblicazione: (2026)
A Note on Fine-Grained Quantum Reductions for Linear Algebraic Problems
di: Doney, Kyle, et al.
Pubblicazione: (2025)
di: Doney, Kyle, et al.
Pubblicazione: (2025)
Improving Merge Sort and Quick Sort Performance by Utilizing Alphadev's Sorting Networks as Base Cases
di: Aly, Anas Gamal, et al.
Pubblicazione: (2025)
di: Aly, Anas Gamal, et al.
Pubblicazione: (2025)
On Detecting $H$-Induced Minors for Small $H$
di: Eagling-Vose, Tala, et al.
Pubblicazione: (2026)
di: Eagling-Vose, Tala, et al.
Pubblicazione: (2026)
Uniformity testing when you have the source code
di: Canonne, Clément L., et al.
Pubblicazione: (2024)
di: Canonne, Clément L., et al.
Pubblicazione: (2024)
On the complexity of symmetric vs. functional PCSPs
di: Nakajima, Tamio-Vesa, et al.
Pubblicazione: (2022)
di: Nakajima, Tamio-Vesa, et al.
Pubblicazione: (2022)
Centrality of shortest paths: Algorithms and complexity results
di: Phosavanh, Johnson, et al.
Pubblicazione: (2024)
di: Phosavanh, Johnson, et al.
Pubblicazione: (2024)
The Sample Complexity of Replicable Realizable PAC Learning
di: Larsen, Kasper Green, et al.
Pubblicazione: (2026)
di: Larsen, Kasper Green, et al.
Pubblicazione: (2026)
Improved Algorithm for Permutation Testing
di: Zhang, Xiaojin
Pubblicazione: (2020)
di: Zhang, Xiaojin
Pubblicazione: (2020)
On the Mysteries of MAX NAE-SAT
di: Brakensiek, Joshua, et al.
Pubblicazione: (2020)
di: Brakensiek, Joshua, et al.
Pubblicazione: (2020)
Removable Online Knapsack and Advice
di: Böckenhauer, Hans-Joachim, et al.
Pubblicazione: (2020)
di: Böckenhauer, Hans-Joachim, et al.
Pubblicazione: (2020)
The Query Complexity of Local Search and Brouwer in Rounds
di: Brânzei, Simina, et al.
Pubblicazione: (2020)
di: Brânzei, Simina, et al.
Pubblicazione: (2020)
Neighborhood-Aware Graph Labeling Problem
di: Shahverdikondori, Mohammad, et al.
Pubblicazione: (2026)
di: Shahverdikondori, Mohammad, et al.
Pubblicazione: (2026)
The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
di: Greilhuber, Jakob, et al.
Pubblicazione: (2025)
di: Greilhuber, Jakob, et al.
Pubblicazione: (2025)
Lazy Kronecker Product
di: Song, Zhao
Pubblicazione: (2026)
di: Song, Zhao
Pubblicazione: (2026)
The Trichotomy of Regular Property Testing
di: Bathie, Gabriel, et al.
Pubblicazione: (2025)
di: Bathie, Gabriel, et al.
Pubblicazione: (2025)
Complexity of Local Search for Euclidean Clustering Problems
di: Manthey, Bodo, et al.
Pubblicazione: (2023)
di: Manthey, Bodo, et al.
Pubblicazione: (2023)
Documenti analoghi
-
Parameterized Shortest Path Reconfiguration
di: Bousquet, Nicolas, et al.
Pubblicazione: (2024) -
On the complexity of constrained reconfiguration and motion planning
di: Bousquet, Nicolas, et al.
Pubblicazione: (2025) -
Parameterized complexity of reconfiguration of atoms
di: Cooper, Alexandre, et al.
Pubblicazione: (2021) -
The tape reconfiguration problem and its consequences for dominating set reconfiguration
di: Bousquet, Nicolas, et al.
Pubblicazione: (2025) -
Kernelization Complexity of Solution Discovery Problems
di: Grobler, Mario, et al.
Pubblicazione: (2024)