A Subexponential Parameterized Algorithm for Proper Interval Completion

DOI10.1137/140988565zbMath1330.68102OpenAlexW2234496216WikidataQ60488386 ScholiaQ60488386MaRDI QIDQ5899484

Fedor V. Fomin, Marcin Pilipczuk, Michał Pilipczuk, Ivan 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

zbMATH Keywords

fixed-parameter tractabilitysubexponential algorithmproper interval graphsproper interval completion

Mathematics Subject Classification ID

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

Related Items (11)

Paths to Trees and Cacti ⋮ Polynomial kernelization for removing induced claws and diamonds ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ A cubic vertex-kernel for \textsc{Trivially Perfect Editing} ⋮ Unit interval editing is fixed-parameter tractable ⋮ Paths to trees and cacti ⋮ Slightly Superexponential Parameterized Problems ⋮ Rank reduction of oriented graphs by vertex and edge deletions ⋮ A polynomial kernel for trivially perfect editing ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs

Cites Work

• Polynomial kernels for proper interval completion and related problems
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Which problems have strongly exponential complexity?
• Two edge modification problems without polynomial kernels
• Faster parameterized algorithms for deletion to split graphs
• An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs
• Optimal greedy algorithms for indifference graphs
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Fast FAST
• Interval Completion Is Fixed Parameter Tractable
• Computing the Minimum Fill-In is NP-Complete
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Subexponential Parameterized Algorithm for Minimum Fill-In
• A Subexponential Parameterized Algorithm for Proper Interval Completion
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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