Imagen de Portada

On the Complexity of Problems on Tree-structured Graphs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bodlaender, Hans L., Groenland, Carla, Jacob, Hugo, Pilipczuk, Marcin, Pilipczuk, Michał
Formato:	Preprint
Publicado:	2022
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

A Note on the Parameterised Complexity of Coverability in Vector Addition Systems
por: Pilipczuk, Michał, et al.
Publicado: (2025)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
por: S., Karthik C., et al.
Publicado: (2023)

The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
por: Bodlaender, Hans L., et al.
Publicado: (2026)

XALP-completeness of Parameterized Problems on Planar Graphs
por: Bodlaender, Hans L., et al.
Publicado: (2024)

A tight quasi-polynomial bound for Global Label Min-Cut
por: Jaffke, Lars, et al.
Publicado: (2022)

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
por: Marx, Dániel, et al.
Publicado: (2026)

On Stable Cutsets in General and Minimum Degree Constrained Graphs
por: Vroon, Mats, et al.
Publicado: (2025)

Graph classes through the lens of logic
por: Pilipczuk, Michał
Publicado: (2025)

On the parameterized complexity of computing tree-partitions
por: Bodlaender, Hans L., et al.
Publicado: (2022)

Coarse Balanced Separators in Fat-Minor-Free Graphs
por: Bonnet, Édouard, et al.
Publicado: (2026)

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

Trade-off between spread and width for tree decompositions
por: Bodlaender, Hans L., et al.
Publicado: (2026)

Hedonic Seat Arrangement Problems
por: Bodlaender, Hans L., et al.
Publicado: (2020)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
por: Focke, Jacob, et al.
Publicado: (2023)

Faster diameter computation in graphs of bounded Euler genus
por: Kluk, Kacper, et al.
Publicado: (2025)

Concurrency Constrained Scheduling with Tree-Like Constraints
por: Bodlaender, Hans L., et al.
Publicado: (2025)

Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
por: Hörsch, Florian, et al.
Publicado: (2025)

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
por: Przybyłek, Michał R., et al.
Publicado: (2026)

Strong odd colorings in graph classes of bounded expansion
por: Pilipczuk, Michał
Publicado: (2025)

Parameterized and approximation algorithms for coverings points with segments in the plane
por: Kowalska, Katarzyna, et al.
Publicado: (2024)

Complexity Aspects of Homomorphisms of Ordered Graphs
por: Čertík, Michal, et al.
Publicado: (2025)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
por: Baril, Ambroise, et al.
Publicado: (2024)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
por: Chudigiewitsch, Florian, et al.
Publicado: (2026)

Parameterized Complexity of the Star Decomposition Problem
por: Hajebi, Sahab, et al.
Publicado: (2024)

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
por: Gartland, Peter, et al.
Publicado: (2023)

On the Complexity of Target Set Selection in Simple Geometric Networks
por: Dvořák, Michal, et al.
Publicado: (2023)

The Computational Complexity of Factored Graphs
por: Gupta, Shreya, et al.
Publicado: (2024)

On the Exact Matching Problem in Dense Graphs
por: Maalouly, Nicolas El, et al.
Publicado: (2024)

Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
por: Majewski, Konrad, et al.
Publicado: (2021)

The Parameterized Complexity of Coloring Mixed Graphs
por: Lauerbach, Antonio, et al.
Publicado: (2026)

Hexasort -- The Complexity of Stacking Colors on Graphs
por: Klocker, Linus, et al.
Publicado: (2026)

On the Complexity of Vertex-Splitting Into an Interval Graph
por: Abu-Khzam, Faisal N., et al.
Publicado: (2026)

Complexity Thresholds for the Constrained Colored Token Swapping Problem
por: Bilò, Davide, et al.
Publicado: (2026)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
por: Cavalar, Bruno P., et al.
Publicado: (2025)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
por: Esmer, Barış Can, et al.
Publicado: (2024)

The Complexity of Contracting Bipartite Graphs into Small Cycles
por: Krithika, R., et al.
Publicado: (2022)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
por: Chang, Hsien-Chih, et al.
Publicado: (2024)

Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree
por: Liu, Brian, et al.
Publicado: (2024)

On the Parameterized Complexity of Semitotal Domination on Graph Classes
por: Retschmeier, Lukas
Publicado: (2025)