Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
From MaRDI portal
Publication:4268849
DOI10.1137/S0097539796303044zbMath0928.68124WikidataQ56430109 ScholiaQ56430109MaRDI QIDQ4268849
Haim Kaplan, Ron Shamir, Robert Endre Tarjan
Publication date: 28 October 1999
Published in: SIAM Journal on Computing (Search for Journal in Brave)
chordal graphsparameterized complexityproper interval graphsstrongly chordal graphsdesign and analysis of algorithmsminimum fill-inphysical mapping of DNA
Nonnumerical algorithms (68W05) Combinatorics on words (68R15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Minimal triangulations of graphs: a survey ⋮ Parameterized coloring problems on chordal graphs ⋮ Planar Disjoint-Paths Completion ⋮ Chordal editing is fixed-parameter tractable ⋮ BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Towards constant-factor approximation for chordal/distance-hereditary vertex deletion ⋮ Planar disjoint-paths completion ⋮ Graphs with maximal induced matchings of the same size ⋮ A Polynomial-Time Algorithm for Outerplanar Diameter Improvement ⋮ Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone ⋮ A polynomial-time algorithm for outerplanar diameter improvement ⋮ Completion to chordal distance-hereditary graphs: a quartic vertex-kernel ⋮ Polynomial kernels for proper interval completion and related problems ⋮ Wheel-Free Deletion Is W[2-Hard] ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ Proper interval vertex deletion ⋮ A cubic vertex-kernel for \textsc{Trivially Perfect Editing} ⋮ Unnamed Item ⋮ A faster FPT algorithm for bipartite contraction ⋮ Faster parameterized algorithms for \textsc{Minimum Fill-in} ⋮ Strongly chordal and chordal bipartite graphs are sandwich monotone ⋮ Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs ⋮ Searching for better fill-in ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ Unit interval editing is fixed-parameter tractable ⋮ Minimal proper interval completions ⋮ Edge deletion problems: branching facilitated by modular decomposition ⋮ Minimum fill-in of sparse graphs: kernelization and approximation ⋮ Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs ⋮ Chordal deletion is fixed-parameter tractable ⋮ On the interval completion of chordal graphs ⋮ Algorithms for automatic ranking of participants and tasks in an anonymized contest ⋮ Complexity classification of some edge modification problems ⋮ Random Generation and Enumeration of Proper Interval Graphs ⋮ Parameterized Enumeration for Modification Problems ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ Unnamed Item ⋮ Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results ⋮ A Subexponential Parameterized Algorithm for Proper Interval Completion ⋮ Parameterized complexity of vertex colouring ⋮ Minimum fill-in: inapproximability and almost tight lower bounds ⋮ Unnamed Item ⋮ Dynamically maintaining split graphs ⋮ Exploring the Subexponential Complexity of Completion Problems ⋮ On the proper intervalization of colored caterpillar trees ⋮ The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs ⋮ Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover ⋮ Unnamed Item ⋮ The Proper Interval Colored Graph problem for caterpillar trees ⋮ Customizable Contraction Hierarchies ⋮ An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs
