Buchumschlag

Polynomial kernels for edge modification problems towards block and strictly chordal graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Dumas, Maël, Perez, Anthony, Rocton, Mathis, Todinca, Ioan
Format:	Preprint
Veröffentlicht:	2022
Schlagworte:	Data Structures and Algorithms Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

On graphs coverable by k shortest paths
von: Dumas, Maël, et al.
Veröffentlicht: (2022)

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

The Computational Complexity of Positive Non-Clashing Teaching in Graphs
von: Ganian, Robert, et al.
Veröffentlicht: (2025)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
von: Esmer, Barış Can, et al.
Veröffentlicht: (2022)

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
von: Ducoffe, Guillaume
Veröffentlicht: (2026)

Deterministic Even-Cycle Detection in Broadcast CONGEST
von: Fraigniaud, Pierre, et al.
Veröffentlicht: (2024)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
von: Kluk, Kacper, et al.
Veröffentlicht: (2025)

On the complexity of global Roman domination problem in graphs
von: Reddy, Sangam Balchandar, et al.
Veröffentlicht: (2026)

Solving Polynomial Equations Over Finite Fields
von: Dell, Holger, et al.
Veröffentlicht: (2024)

The Quasi-Polynomial Low-Degree Conjecture is False
von: Buhai, Rares-Darius, et al.
Veröffentlicht: (2025)

A note on the complexity of the picker routing problem in multi-block warehouses and related problems
von: Prunet, Thibault, et al.
Veröffentlicht: (2023)

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
von: Dell, Holger, et al.
Veröffentlicht: (2022)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
von: Sajith, Thejas Radhika
Veröffentlicht: (2025)

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
von: Asadi, Vahid R., et al.
Veröffentlicht: (2026)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
von: Jiang, Cheng, et al.
Veröffentlicht: (2026)

An alignment problem
von: McDaniel, Emma L., et al.
Veröffentlicht: (2024)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
von: Chakraborty, Dibyayan, et al.
Veröffentlicht: (2024)

The complexity of testing all properties of planar graphs, and the role of isomorphism
von: Basu, Sabyasachi, et al.
Veröffentlicht: (2021)

Algorithms and complexity for monitoring edge-geodetic sets in graphs
von: Foucaud, Florent, et al.
Veröffentlicht: (2024)

Constructing self-referential instances for the clique problem
von: Li, Jiaqi, et al.
Veröffentlicht: (2026)

Channel allocation revisited through 1-extendability of graphs
von: Busson, Anthony, et al.
Veröffentlicht: (2024)

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
von: Austrin, Per, et al.
Veröffentlicht: (2024)

Twin-Width Meets Feedback Edges and Vertex Integrity
von: Balabán, Jakub, et al.
Veröffentlicht: (2024)

The Parameterized Complexity Landscape of the Unsplittable Flow Problem
von: Ganian, Robert, et al.
Veröffentlicht: (2024)

An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem
von: Yang, Yang
Veröffentlicht: (2025)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
von: Yang, Yang
Veröffentlicht: (2024)

A lossless a priori splitting rule for split-delivery routing problems
von: Jones, Bo, et al.
Veröffentlicht: (2025)

On the Advantage of Adaptivity for Sampling with Cell Probes
von: Byramji, Farzan, et al.
Veröffentlicht: (2026)

Resource Leveling: Complexity of a UET two-processor scheduling variant and related problems
von: Bendotti, Pascale, et al.
Veröffentlicht: (2024)

PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
von: Scheder, Dominik, et al.
Veröffentlicht: (2025)

Smoothed analysis for graph isomorphism
von: Anastos, Michael, et al.
Veröffentlicht: (2024)

The stochastic block model has the overlap graph property for modularity
von: Bhamidi, Shankar, et al.
Veröffentlicht: (2026)

Trickle-down Theorems via C-Lorentzian Polynomials II: Pairwise Spectral Influence and Improved Dobrushin's Condition
von: Leake, Jonathan, et al.
Veröffentlicht: (2025)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Polynomial-Time Pseudodeterministic Construction of Primes
von: Chen, Lijie, et al.
Veröffentlicht: (2023)

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
von: Leake, Jonathan, et al.
Veröffentlicht: (2025)

Polynomial-time sampling despite disorder chaos
von: Ma, Eric, et al.
Veröffentlicht: (2025)

Polynomial-time tolerant testing stabilizer states
von: Arunachalam, Srinivasan, et al.
Veröffentlicht: (2024)