Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs

DOI10.1007/978-3-540-77120-3_76MaRDI QIDQ5387822zbMATH OpenOpenAlexFDO

Authors F. Mancini

Publication date 27 May 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77120-3_76

Mathematics Subject Classification ID

Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
• Exact Algorithms for Treewidth and Minimum Fill-In
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• scientific article; zbMATH DE number 7053390
• The decomposability of minimum fill-in problems for graphs

Cites work

• A completely dynamic algorithm for split graphs
• Chordal Deletion Is Fixed-Parameter Tractable
• Complexity classification of some edge modification problems
• Complexity of Finding Embeddings in a k-Tree
• Computing the Minimum Fill-In is NP-Complete
• Counting clique trees and computing perfect elimination schemes in parallel
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 1107728 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• Interval Completion Is Fixed Parameter Tractable
• Minimal Split Completions of Graphs
• Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
• Minimal triangulations of graphs: a survey
• Obtaining a Planar Graph by Vertex Deletion
• On generating all maximal independent sets
• On rigid circuit graphs
• Parameterized and Exact Computation
• Parameterized coloring problems on chordal graphs
• Parameterized complexity of vertex colouring
• SOFSEM 2005: Theory and Practice of Computer Science
• The splittance of a graph
• The Use of Linear Graphs in Gauss Elimination
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Vertex Coloring of Comparability+ke and –ke Graphs

Cited in

(4)

• \(K_{a,k}\) minors in graphs of bounded tree-width
• Characterizing and Computing Minimal Cograph Completions
• Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
• Characterizing and computing minimal cograph completions

This page was built for publication: Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs

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