Copertina

$O(n +f(k))$: Truly Linear FPT

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bumpus, Benjamin Merlin, Downey, Rod, Eagling-Vose, Tala, Enright, Jessica, Fellows, Michael R., Kutner, David C., Larios-Jones, Laura, Martin, Barnaby, Rosamond, Frances, Yates, Ella
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity Discrete Mathematics Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification
di: Eagling-Vose, Tala, et al.
Pubblicazione: (2025)

Steiner Forest for $H$-Subgraph-Free Graphs
di: Eagling-Vose, Tala, et al.
Pubblicazione: (2026)

Finding d-Cuts in Claw-free Graphs
di: Ahn, Jungho, et al.
Pubblicazione: (2025)

Finding $d$-Cuts in Probe $H$-Free Graphs
di: Dabrowski, Konrad K., et al.
Pubblicazione: (2025)

Temporal Reachability Dominating Sets: contagion in temporal graphs
di: Kutner, David C., et al.
Pubblicazione: (2023)

Optimal b-Colourings and Fall Colourings in $H$-Free Graphs
di: Ahn, Jungho, et al.
Pubblicazione: (2026)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
di: Eagling-Vose, Tala, et al.
Pubblicazione: (2025)

Graph Homomorphism, Monotone Classes and Bounded Pathwidth
di: Eagling-Vose, Tala, et al.
Pubblicazione: (2024)

On Detecting $H$-Induced Minors for Small $H$
di: Eagling-Vose, Tala, et al.
Pubblicazione: (2026)

Better late, then? The hardness of choosing delays to meet passenger demands in temporal graphs
di: Kutner, David C., et al.
Pubblicazione: (2025)

Reconfigurable routing in data center networks
di: Kutner, David C., et al.
Pubblicazione: (2024)

Non-crossing $H$-graphs: a generalization of proper interval graphs admitting FPT algorithms
di: Bonomo-Braberman, Flavia, et al.
Pubblicazione: (2025)

Approximating temporal modularity on graphs of small underlying treewidth
di: Agdur, Vilhelm, et al.
Pubblicazione: (2025)

Bounding Width on Graph Classes of Constant Diameter
di: Dabrowski, Konrad K., et al.
Pubblicazione: (2025)

Directed branch-width: A directed analogue of tree-width
di: Bumpus, Benjamin Merlin, et al.
Pubblicazione: (2020)

Restricted CSPs and F-free Digraph Algorithmics
di: Guzmán-Pro, Santiago, et al.
Pubblicazione: (2025)

Atropos-k is PSPACE-complete
di: Yang, Chao, et al.
Pubblicazione: (2024)

Payment Scheduling in the Interval Debt Model
di: Friedetzky, Tom, et al.
Pubblicazione: (2024)

On the satisfiability of random $3$-SAT formulas with $k$-wise independent clauses
di: Caragiannis, Ioannis, et al.
Pubblicazione: (2024)

A Linear Kernel for Planar Vector Domination
di: Sahili, Mahabba El, et al.
Pubblicazione: (2023)

Temporal Orienteering with Changing Fuel Costs
di: Corsini, Timothée, et al.
Pubblicazione: (2025)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
di: Johnson, Matthew, et al.
Pubblicazione: (2022)

Reachability in temporal graphs under perturbation
di: Enright, Jessica, et al.
Pubblicazione: (2024)

Parameterised algorithms for temporally satisfying reconfiguration problems
di: Davot, Tom, et al.
Pubblicazione: (2025)

Maximum $k$- vs. $\ell$-colourings of graphs
di: Nakajima, Tamio-Vesa, et al.
Pubblicazione: (2023)

Small unsatisfiable $k$-CNFs with bounded literal occurrence
di: Zhang, Tianwei, et al.
Pubblicazione: (2024)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
di: Hirahara, Shuichi, et al.
Pubblicazione: (2025)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
di: Hirahara, Shuichi, et al.
Pubblicazione: (2024)

The complexity of strong conflict-free vertex-connection $k$-colorability
di: Hsieh, Sun-Yuan, et al.
Pubblicazione: (2024)

Families of tractable problems with respect to vertex-interval-membership width and its generalisations
di: Enright, Jessica, et al.
Pubblicazione: (2025)

Structural Parameters for Dense Temporal Graphs
di: Enright, Jessica, et al.
Pubblicazione: (2024)

Lower Bounds for Linear Operators
di: Ko, Young Kun
Pubblicazione: (2025)

Fractional Linear Matroid Matching is in quasi-NC
di: Gurjar, Rohit, et al.
Pubblicazione: (2024)

On graphs coverable by k shortest paths
di: Dumas, Maël, et al.
Pubblicazione: (2022)

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
di: Armand, Jules, et al.
Pubblicazione: (2025)

On the enumeration of Tarski fixed points
di: Müller, Julian
Pubblicazione: (2023)

Edge-Disjoint Paths in Eulerian Digraphs
di: Cavallaro, Dario, et al.
Pubblicazione: (2024)

Monotone Bounded-Depth Complexity of Homomorphism Polynomials
di: Bhargav, C. S., et al.
Pubblicazione: (2025)

Relations between monotone complexity measures based on decision tree complexity
di: Byramji, Farzan, et al.
Pubblicazione: (2024)

Gap Preserving Reductions Between Reconfiguration Problems
di: Ohsaka, Naoto
Pubblicazione: (2022)