Copertina

A $O^*((2 + ε)^k)$ Time Algorithm for Cograph Deletion Using Unavoidable Subgraphs in Large Prime Graphs

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Lafond, Manuel, Sarrazin, Francis
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Cluster Editing on Cographs and Related Classes
di: Lafond, Manuel, et al.
Pubblicazione: (2024)

Improved Kernelization and Fixed-parameter Algorithms for Bicluster Editing
di: Lafond, Manuel
Pubblicazione: (2024)

Search-Space Reduction Via Essential Vertices Revisited: Vertex Multicut and Cograph Deletion
di: Jansen, Bart M. P., et al.
Pubblicazione: (2024)

The Parameterized Landscape of Labeled Graph Contractions
di: Lafond, Manuel, et al.
Pubblicazione: (2025)

Path Partitions of Phylogenetic Networks
di: Lafond, Manuel, et al.
Pubblicazione: (2024)

Scalable $k$-clique Densest Subgraph Search
di: Ye, Xiaowei, et al.
Pubblicazione: (2024)

Pathfinding in Self-Deleting Graphs
di: Dvořák, Michal, et al.
Pubblicazione: (2025)

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

Novel Complexity Results for Temporal Separators with Deadlines
di: Dondi, Riccardo, et al.
Pubblicazione: (2025)

New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph
di: Ameli, Afrouz Jabal, et al.
Pubblicazione: (2026)

Median and Small Parsimony Problems on RNA trees
di: Marchand, Bertrand, et al.
Pubblicazione: (2024)

Cluster Vertex Deletion on Chordal Graphs
di: Cao, Yixin, et al.
Pubblicazione: (2026)

Algorithms and Complexity of Hedge Cluster Deletion Problems
di: Konstantinidis, Athanasios L., et al.
Pubblicazione: (2025)

Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density
di: Bentert, Matthias, et al.
Pubblicazione: (2026)

New Parallel and Streaming Algorithms for Directed Densest Subgraph
di: Mitrović, Slobodan, et al.
Pubblicazione: (2025)

Classes Testable with $O(1/ε)$ Queries for Small $ε$ Independent of the Number of Variables
di: Bshouty, Nader H., et al.
Pubblicazione: (2026)

On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions
di: Chandrasekaran, Karthekeyan, et al.
Pubblicazione: (2025)

A $(1+ε)$-Approximation for Ultrametric Embedding in Subquadratic Time
di: Bathie, Gabriel, et al.
Pubblicazione: (2025)

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

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
di: Mao, Xiao
Pubblicazione: (2023)

A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
di: Çivril, Ali
Pubblicazione: (2023)

An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery
di: Xu, Xiaojia, et al.
Pubblicazione: (2024)

Finding Induced Subgraphs from Graphs with Small Mim-Width
di: Otachi, Yota, et al.
Pubblicazione: (2024)

A Note on Approximability of Densest At-Least-k-Subgraph
di: Laekhanukit, Bundit, et al.
Pubblicazione: (2026)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
di: Dai, Han, et al.
Pubblicazione: (2025)

Quadratic-Time Algorithm for the Maximum-Weight $(k, \ell)$-Sparse Subgraph Problem
di: Deák, Bence, et al.
Pubblicazione: (2025)

A simple $(2+ε)$-approximation for knapsack interdiction
di: Weninger, Noah
Pubblicazione: (2026)

Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems
di: Esmer, Barış Can, et al.
Pubblicazione: (2024)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
di: Cohen-Addad, Vincent, et al.
Pubblicazione: (2025)

Approximate Minimum Sum Colorings and Maximum $k$-Colorable Subgraphs of Chordal Graphs
di: DeHaan, Ian, et al.
Pubblicazione: (2024)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
di: Solomon, Shay, et al.
Pubblicazione: (2023)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2023)

Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
di: Norose, Ryoma, et al.
Pubblicazione: (2024)

Beyond 2-approximation for k-Center in Graphs
di: Jin, Ce, et al.
Pubblicazione: (2025)

Weighted $k$-Path and Other Problems in Almost $O^*(2^k)$ Deterministic Time via Dynamic Representative Sets
di: Nederlof, Jesper
Pubblicazione: (2025)

Finding Order-Preserving Subgraphs
di: Imamura, Haruya, et al.
Pubblicazione: (2025)

Forbidden Subgraph Problems with Predictions
di: Böckenhauer, Hans-Joachim, et al.
Pubblicazione: (2025)

Destroying Densest Subgraphs is Hard
di: Bazgan, Cristina, et al.
Pubblicazione: (2024)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
di: Kadria, Avi, et al.
Pubblicazione: (2025)

The SpaceSaving$\pm$ Family of Algorithms for Data Streams with Bounded Deletions
di: Zhao, Fuheng, et al.
Pubblicazione: (2023)