Copertina

Robust Contraction Decomposition for Minor-Free Graphs and its Applications

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bandyapadhyay, Sayan, Lochet, William, Lokshtanov, Daniel, Marx, Dániel, Misra, Pranabendu, Neuen, Daniel, Saurabh, Saket, Tale, Prafullkumar, Xue, Jie
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms Discrete Mathematics Combinatorics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Path Contraction Faster than $2^n$
di: Agrawal, Akanksha, et al.
Pubblicazione: (2025)

A Finer View of the Parameterized Landscape of Labeled Graph Contractions
di: Mathur, Yashaswini, et al.
Pubblicazione: (2025)

A Single Exponential-Time FPT Algorithm for Cactus Contraction
di: Krithika, R., et al.
Pubblicazione: (2025)

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

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
di: Bandyapadhyay, Sayan, et al.
Pubblicazione: (2023)

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

Parameterized Saga of First-Fit and Last-Fit Coloring
di: Agrawal, Akanksha, et al.
Pubblicazione: (2024)

Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
di: Neuen, Daniel
Pubblicazione: (2020)

A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST
di: Jana, Satyabrata, et al.
Pubblicazione: (2025)

Robust Graph Isomorphism, Quadratic Assignment and VC Dimension
di: Dahan, Anatole, et al.
Pubblicazione: (2026)

Isomorphism Testing Parameterized by Genus and Beyond
di: Neuen, Daniel
Pubblicazione: (2021)

Isomorphism for Tournaments of Small Twin Width
di: Grohe, Martin, et al.
Pubblicazione: (2023)

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
di: Chakraborty, Dipayan, et al.
Pubblicazione: (2024)

Parameterized complexity of isometric path partition: treewidth and diameter
di: Chakraborty, Dibyayan, et al.
Pubblicazione: (2025)

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
di: Foucaud, Florent, et al.
Pubblicazione: (2026)

A Faster Isomorphism Test for Graphs of Small Degree
di: Grohe, Martin, et al.
Pubblicazione: (2018)

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

Space Efficient Algorithms for Parameterised Problems
di: Akhtar, Sheikh Shakil, et al.
Pubblicazione: (2025)

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

Efficient Approximation of Fractional Hypertree Width
di: Korchemna, Viktoriia, et al.
Pubblicazione: (2024)

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
di: Grohe, Martin, et al.
Pubblicazione: (2023)

Polynomial Kernels for Spanning Tree with Diversity Requirements
di: Golovach, Petr A., et al.
Pubblicazione: (2026)

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
di: Tale, Prafullkumar
Pubblicazione: (2025)

The Iteration Number of the Weisfeiler-Leman Algorithm
di: Grohe, Martin, et al.
Pubblicazione: (2023)

The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
di: Bentert, Matthias, et al.
Pubblicazione: (2024)

Double Exponential Lower Bound for Telephone Broadcast
di: Tale, Prafullkumar
Pubblicazione: (2024)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
di: Foucaud, Florent, et al.
Pubblicazione: (2023)

Metric Dimension and Geodetic Set Parameterized by Vertex Cover
di: Foucaud, Florent, et al.
Pubblicazione: (2024)

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

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
di: Lokshtanov, Daniel, et al.
Pubblicazione: (2024)

Parameterized Approximation for Capacitated $d$-Hitting Set with Hard Capacities
di: Lokshtanov, Daniel, et al.
Pubblicazione: (2024)

Subexponential Parameterized Algorithms for Hitting Subgraphs
di: Lokshtanov, Daniel, et al.
Pubblicazione: (2024)

Distance Approximating Minors for Planar and Minor-Free Graphs
di: Chang, Hsien-Chih, et al.
Pubblicazione: (2025)

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

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

Colouring Probe $H$-Free Graphs
di: Paulusma, Daniël, et al.
Pubblicazione: (2025)

On a tree-based variant of bandwidth and forbidding simple topological minors
di: Jacob, Hugo, et al.
Pubblicazione: (2025)

An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching
di: Bandyapadhyay, Sayan, et al.
Pubblicazione: (2024)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
di: Paul-Pena, Daniel, et al.
Pubblicazione: (2024)

A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
di: Paul-Pena, Daniel, et al.
Pubblicazione: (2022)