A Subexponential Parameterized Algorithm for Proper Interval Completion
DOI10.1137/140988565zbMATH Open1330.68102DBLPjournals/siamdm/BliznetsFPP15OpenAlexW2234496216WikidataQ60488386 ScholiaQ60488386MaRDI QIDQ5899484FDOQ5899484
Fedor V. Fomin, Marcin Pilipczuk, MichaΕ Pilipczuk, I. A. Bliznets
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
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Which problems have strongly exponential complexity?
- Optimal greedy algorithms for indifference graphs
- 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
- 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
- An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs
- A Subexponential Parameterized Algorithm for Proper Interval Completion
Cited In (13)
- 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 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}
- Paths to Trees and Cacti
Recommendations
- Title not available (Why is that?) π π
- Title not available (Why is that?) π π
- Subexponential Parameterized Algorithm for Minimum Fill-In π π
- An ${\mathcal{O}}(n^2)$ -time Algorithm for the Minimal Interval Completion Problem π π
- Interval Completion Is Fixed Parameter Tractable π π
- An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem π π
- Subexponential parameterized algorithm for Interval Completion π π
- A new fully polynomial time approximation scheme for the interval subset sum problem π π
- Subexponential Parameterized Algorithm for I <scp>nterval</scp> C <scp>ompletion</scp> π π
- A Subexponential Parameterized Algorithm for Proper Interval Completion π π
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)
