Minimum fill-in of sparse graphs: kernelization and approximation

DOI10.1007/s00453-013-9776-1zbMath1310.68106OpenAlexW2061643569WikidataQ60488431 ScholiaQ60488431MaRDI QIDQ2258069

Yngve Villanger, Fedor V. Fomin, Geevarghese Philip

Publication date: 2 March 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2011/3345/

zbMATH Keywords

planar graphsparameterized complexitykernelization\(d\)-degenerate graphsminimum fill-inlinear kernel

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (3)

On the generalized AOR and CG iteration methods for a class of block two-by-two linear systems ⋮ Learning chordal extensions ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Faster parameterized algorithms for \textsc{Minimum Fill-in}
• On rigid circuit graphs
• Minimal triangulations of graphs: a survey
• Decomposition by clique separators
• Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
• Chordal completions of planar graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Characterizations and algorithmic applications of chordal graph embeddings
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• The extremal function for complete minors
• Parametrized complexity theory.
• On tree width, bramble size, and expansion
• Minimum Fill-in of Sparse Graphs: Kernelization and Approximation
• Polynomial-time data reduction for dominating set
• Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
• Computing the Minimum Fill-In is NP-Complete
• Algorithmic Aspects of Vertex Elimination on Graphs
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
• On Representatives of Subsets
• (Meta) Kernelization
• A wide-range algorithm for minimal triangulation from an arbitrary ordering

This page was built for publication: Minimum fill-in of sparse graphs: kernelization and approximation