Interval Completion Is Fixed Parameter Tractable
From MaRDI portal
Publication:3642873
DOI10.1137/070710913zbMath1227.05241OpenAlexW2086331454WikidataQ56267431 ScholiaQ56267431MaRDI QIDQ3642873
Pinar Heggernes, Jan Arne Telle, Christophe Paul, Yngve Villanger
Publication date: 6 November 2009
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/070710913
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (32)
On the effectiveness of the incremental approach to minimal chordal edge modification ⋮ Vertex deletion into bipartite permutation graphs ⋮ Note on maximal bisection above tight lower bound ⋮ Polynomial kernels for proper interval completion and related problems ⋮ Sublinear approximation algorithms for boxicity and related problems ⋮ Characterizing and Computing Minimal Cograph Completions ⋮ Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ A probabilistic approach to problems parameterized above or below tight bounds ⋮ Proper interval vertex deletion ⋮ Solving MAX-\(r\)-SAT above a tight lower bound ⋮ Betweenness parameterized above tight lower bound ⋮ A faster FPT algorithm for bipartite contraction ⋮ Note on Max Lin-2 above average ⋮ Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs ⋮ Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes ⋮ Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs ⋮ Characterizing and computing minimal cograph completions ⋮ Slightly Superexponential Parameterized Problems ⋮ Vertex deletion into bipartite permutation graphs ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ Proper Interval Vertex Deletion ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ A Subexponential Parameterized Algorithm for Proper Interval Completion ⋮ Minimum fill-in: inapproximability and almost tight lower bounds ⋮ Polynomial Kernels for Proper Interval Completion and Related Problems ⋮ Dynamically maintaining split graphs ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ Exploring the Subexponential Complexity of Completion Problems ⋮ Scale free interval graphs ⋮ Unnamed Item
This page was built for publication: Interval Completion Is Fixed Parameter Tractable
