Imagen de Portada

Computing Tree Decompositions with Small Independence Number

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Dallard, Clément, Fomin, Fedor V., Golovach, Petr A., Korhonen, Tuukka, Milanič, Martin
Formato:	Preprint
Publicado:	2022
Materias:	Data Structures and Algorithms Combinatorics
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
por: Korhonen, Tuukka
Publicado: (2024)

Stability in Graphs with Matroid Constraints
por: Fomin, Fedor V., et al.
Publicado: (2024)

Fixed-Parameter Tractability of Hedge Cut
por: Fomin, Fedor V., et al.
Publicado: (2024)

On constrained intersection representations of graphs and digraphs
por: Cicalese, Ferdinando, et al.
Publicado: (2025)

Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
por: Bodlaender, Hans L., et al.
Publicado: (2025)

Cuts in Graphs with Matroid Constraints
por: Banik, Aritra, et al.
Publicado: (2024)

Minor Containment and Disjoint Paths in almost-linear time
por: Korhonen, Tuukka, et al.
Publicado: (2024)

A Framework for Parameterized Subexponential-Subcubic-Time Algorithms for Weighted Problems in Planar Graphs
por: Bentert, Matthias, et al.
Publicado: (2026)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
por: Bentert, Matthias, et al.
Publicado: (2024)

Edge Clique Partition and Cover Beyond Independence
por: Fomin, Fedor V., et al.
Publicado: (2025)

Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
por: Fomin, Fedor V., et al.
Publicado: (2024)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
por: Korhonen, Tuukka, et al.
Publicado: (2024)

Packing Short Cycles
por: Bentert, Matthias, et al.
Publicado: (2024)

Algorithmic Extensions of Dirac's Theorem
por: Fomin, Fedor V., et al.
Publicado: (2020)

Dynamic Treewidth in Logarithmic Time
por: Korhonen, Tuukka
Publicado: (2025)

When does FTP become FPT?
por: Bentert, Matthias, et al.
Publicado: (2025)

Fault-Tolerant Matroid Bases
por: Bentert, Matthias, et al.
Publicado: (2025)

H-Planarity and Parametric Extensions: when Modulators Act Globally
por: Fomin, Fedor V., et al.
Publicado: (2025)

Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization
por: Fomin, Fedor V., et al.
Publicado: (2025)

Parameterized Geometric Graph Modification with Disk Scaling
por: Fomin, Fedor V., et al.
Publicado: (2024)

Hybrid k-Clustering: Blending k-Median and k-Center
por: Fomin, Fedor V., et al.
Publicado: (2024)

Algorithms for Euclidean Distance Matrix Completion: Exploiting Proximity to Triviality
por: Fomin, Fedor V., et al.
Publicado: (2026)

Connectivity augmentation is fixed-parameter tractable
por: Korhonen, Tuukka, et al.
Publicado: (2026)

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
por: Bai, Tian, et al.
Publicado: (2026)

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

What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing
por: Blin, Lélia, et al.
Publicado: (2024)

When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations
por: Bentert, Matthias, et al.
Publicado: (2025)

Tree Independence Number IV. Even-hole-free Graphs
por: Chudnovsky, Maria, et al.
Publicado: (2024)

Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs
por: Galby, Esther, et al.
Publicado: (2023)

The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs
por: Beisegel, Jesse, et al.
Publicado: (2024)

Sandwich Monotonicity and the Recognition of Weighted Graph Classes
por: Beisegel, Jesse, et al.
Publicado: (2025)

A Unified View of Graph Regularity via Matrix Decompositions
por: Bodwin, Greg, et al.
Publicado: (2019)

Branch-width of connectivity functions is fixed-parameter tractable
por: Korhonen, Tuukka, et al.
Publicado: (2026)

Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
por: Bonnet, Édouard, et al.
Publicado: (2023)

On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers
por: Chalermsook, Parinya, et al.
Publicado: (2025)

Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids and Beyond
por: Kobayashi, Yasuaki, et al.
Publicado: (2023)

Improved exploration of temporal graphs
por: Bastide, Paul, et al.
Publicado: (2025)

A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
por: Bourneuf, Romain, et al.
Publicado: (2025)

Dynamic Meta-Kernelization
por: Bertram, Christian, et al.
Publicado: (2025)

Induced Minors and Coarse Tree Decompositions
por: Chudnovsky, Maria, et al.
Publicado: (2026)