A Subexponential Parameterized Algorithm for Proper Interval Completion

DOI10.1137/140988565zbMATH Open1330.68102DBLPjournals/siamdm/BliznetsFPP15OpenAlexW2234496216WikidataQ60488386 ScholiaQ60488386MaRDI QIDQ5899484FDOQ5899484

Authors I. A. Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michał Pilipczuk 

Publication date 30 October 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/140988565

zbMATH Keywords

fixed-parameter tractabilityproper interval graphssubexponential algorithmproper interval completion

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• A subexponential parameterized algorithm for proper interval completion
• Subexponential parameterized algorithm for interval completion
• Subexponential parameterized algorithm for {\textsc{Interval Completion}}
• Interval Completion Is Fixed Parameter Tractable
• A new fully polynomial time approximation scheme for the interval subset sum problem
• An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem
• Exploring subexponential parameterized complexity of completion problems
• An \({\mathcal{O}}(n^2)\)-time algorithm for the minimal interval completion problem
• Subexponential parameterized algorithm for minimum fill-in
• scientific article; zbMATH DE number 7053390

Cites work

• scientific article; zbMATH DE number 1617243 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A subexponential parameterized algorithm for proper interval completion
• An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs
• Computing the Minimum Fill-In is NP-Complete
• Exploring subexponential parameterized complexity of completion problems
• Fast FAST
• Faster parameterized algorithms for deletion to split graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Interval Completion Is Fixed Parameter Tractable
• Optimal greedy algorithms for indifference graphs
• Polynomial kernels for proper interval completion and related problems
• Subexponential parameterized algorithm for minimum fill-in
• Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
• 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

(16)

• On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
• Polynomial kernels for proper interval completion and related problems
• Slightly superexponential parameterized problems
• Polynomial kernels for proper interval completion and related problems
• Subexponential parameterized algorithm for {\textsc{Interval Completion}}
• Approximation and kernelization for chordal vertex deletion
• Subexponential parameterized algorithm for interval completion
• Interval Completion Is Fixed Parameter Tractable
• Rank reduction of oriented graphs by vertex and edge deletions
• Polynomial kernelization for removing induced claws and diamonds
• A survey of parameterized algorithms and the complexity of edge modification
• A subexponential parameterized algorithm for proper interval completion
• On the proper interval completion problem within some chordal subclasses
• A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
• Paths to trees and cacti
• Paths to trees and cacti

This page was built for publication: A Subexponential Parameterized Algorithm for Proper Interval Completion

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