Interval Completion Is Fixed Parameter Tractable

DOI10.1137/070710913MaRDI QIDQ3642873zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Yngve Villanger, Pinar Heggernes, Christophe Paul, Jan Arne Telle

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

zbMATH Keywords

branchingedge completionFPT algorithminterval graphsprofile minimization

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• A subexponential parameterized algorithm for proper interval completion
• A Subexponential Parameterized Algorithm for Proper Interval Completion
• scientific article; zbMATH DE number 125608
• Subexponential parameterized algorithm for interval completion
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Subexponential parameterized algorithm for {\textsc{Interval Completion}}
• Interval deletion is fixed-parameter tractable
• Interval deletion is fixed-parameter tractable
• scientific article; zbMATH DE number 1262811
• Approximated fixed points via completion

Cited in

(39)

• Dynamically maintaining split graphs
• Scale free interval graphs
• Note on maximal bisection above tight lower bound
• Sublinear approximation algorithms for boxicity and related problems
• Proper interval vertex deletion
• Betweenness parameterized above tight lower bound
• Subexponential parameterized algorithms and kernelization on almost chordal graphs
• Vertex deletion into bipartite permutation graphs
• Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
• Minimum fill-in: inapproximability and almost tight lower bounds
• Open problems on graph coloring for special graph classes
• Exploring the subexponential complexity of completion problems
• Proper Interval Vertex Deletion
• Polynomial kernels for proper interval completion and related problems
• Fixed-Parameter Complexity of Minimum Profile Problems
• Characterizing and Computing Minimal Cograph Completions
• On interval graphs and matrice profiles
• Polynomial kernels for proper interval completion and related problems
• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
• Subexponential parameterized algorithm for {\textsc{Interval Completion}}
• Linear recognition of almost interval graphs
• Subexponential parameterized algorithm for interval completion
• Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
• scientific article; zbMATH DE number 7053390 (Why is no real title available?)
• Slightly superexponential parameterized problems
• scientific article; zbMATH DE number 7651188 (Why is no real title available?)
• A Subexponential Parameterized Algorithm for Proper Interval Completion
• Vertex deletion into bipartite permutation graphs
• A survey of parameterized algorithms and the complexity of edge modification
• A probabilistic approach to problems parameterized above or below tight bounds
• Solving MAX-\(r\)-SAT above a tight lower bound
• A graph-theoretic barcode ordering model for linked-reads
• Note on Max Lin-2 above average
• Parameterized dynamic data structure for split completion
• An update on pushable homomorphisms
• On the effectiveness of the incremental approach to minimal chordal edge modification
• Fixed-parameter complexity of minimum profile problems
• Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
• Characterizing and computing minimal cograph completions

This page was built for publication: Interval Completion Is Fixed Parameter Tractable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3642873)