Exploring the subexponential complexity of completion problems
From MaRDI portal
Publication:2828210
Recommendations
Cites work
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
- A partial k-arboretum of graphs with bounded treewidth
- A subexponential parameterized algorithm for proper interval completion
- Cluster editing with locally bounded modifications
- Computing the Minimum Fill-In is NP-Complete
- Edge-Deletion Problems
- Fast FAST
- Faster parameterized algorithms for deletion to split graphs
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Graph Classes: A Survey
- Incompressibility of \(H\)-free edge modification problems
- Interval Completion Is Fixed Parameter Tractable
- Linear recognition of pseudo-split graphs
- NP-completeness results for edge modification problems
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- Quasi-threshold graphs
- Subexponential parameterized algorithm for minimum fill-in
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- Threshold graphs and related topics
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Two edge modification problems without polynomial kernels
- Which problems have strongly exponential complexity?
Cited in
(11)- On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
- Approximation and kernelization for chordal vertex deletion
- Rank reduction of oriented graphs by vertex and edge deletions
- A survey of parameterized algorithms and the complexity of edge modification
- Exploring subexponential parameterized complexity of completion problems
- Dichotomy results on the hardness of \(H\)-free edge modification problems
- Polynomial kernelization for removing induced claws and diamonds
- A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
- scientific article; zbMATH DE number 7471715 (Why is no real title available?)
- Diameter estimates for graph associahedra
- (Sub)linear kernels for edge modification problems toward structured graph classes
This page was built for publication: Exploring the subexponential complexity of completion problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828210)
