Minimum fill-in and treewidth of split + ke and split +kv graphs

DOI10.1016/J.DAM.2008.11.006MaRDI QIDQ972334zbMATH OpenOpenAlexFDO

Authors F. Mancini

Publication date 25 May 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2008.11.006

zbMATH Keywords

treewidthparameterized algorithmssplit graphsminimum fill-in

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
• Exact Algorithms for Treewidth and Minimum Fill-In
• Minimum fill-in of sparse graphs: kernelization and approximation
• Minimum fill-in of sparse graphs: kernelization and approximation
• scientific article; zbMATH DE number 1185971

Cites work

• 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 1161563 (Why is no real title available?)
• Chordal Deletion Is Fixed-Parameter Tractable
• Complexity classification of some edge modification problems
• Complexity of Finding Embeddings in a k-Tree
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Computing the Minimum Fill-In is NP-Complete
• Counting clique trees and computing perfect elimination schemes in parallel
• Dynamically maintaining split graphs
• Edge coloring nearly bipartite graphs
• Error compensation in leaf power problems
• Faster Parameterized Algorithms for Minimum Fill-In
• Finding odd cycle transversals.
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Graph-Theoretic Concepts in Computer Science
• Improved Algorithms for the Feedback Vertex Set Problems
• Interval Completion Is Fixed Parameter Tractable
• 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 the interval completion of chordal 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 Use of Linear Graphs in Gauss Elimination
• The splittance of a graph
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Vertex Coloring of Comparability+ke and –ke Graphs

Cited in

(4)

• On the effectiveness of the incremental approach to minimal chordal edge modification
• Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
• Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques
• Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques

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 Q972334)