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
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
fixed-parameter tractabilityproper interval graphssubexponential algorithmproper interval completion
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Title not available (Why is that?)
- Which problems have strongly exponential complexity?
- Optimal greedy algorithms for indifference graphs
- Title not available (Why is that?)
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Computing the Minimum Fill-In is NP-Complete
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Fast FAST
- Subexponential parameterized algorithm for minimum fill-in
- Title not available (Why is that?)
- Interval Completion Is Fixed Parameter Tractable
- Polynomial kernels for proper interval completion and related problems
- Faster parameterized algorithms for deletion to split graphs
- Two edge modification problems without polynomial kernels
- Title not available (Why is that?)
- An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs
- A subexponential parameterized algorithm for proper interval completion
Cited In (16)
- Polynomial kernels for proper interval completion and related problems
- Slightly Superexponential Parameterized Problems
- Paths to trees and cacti
- On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
- Rank reduction of oriented graphs by vertex and edge deletions
- Unit interval editing is fixed-parameter tractable
- A subexponential parameterized algorithm for proper interval completion
- A survey of parameterized algorithms and the complexity of edge modification
- A polynomial kernel for trivially perfect editing
- On the proper interval completion problem within some chordal subclasses
- Interval Completion Is Fixed Parameter Tractable
- Approximation and Kernelization for Chordal Vertex Deletion
- Polynomial kernelization for removing induced claws and diamonds
- A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
- Polynomial kernels for proper interval completion and related problems
- 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)
