Iterative Compression and Exact Algorithms

DOI10.1007/978-3-540-85238-4_27MaRDI QIDQ3599139zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Fedor V. Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Saket Saurabh

Publication date 3 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85238-4_27

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Recommendations

• Iterative compression and exact algorithms
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• A complexity dichotomy for finding disjoint solutions of vertex deletion problems
• A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
• Efficient exact algorithms through enumerating maximal independent sets and other techniques

Cites work

• scientific article; zbMATH DE number 5485529 (Why is no real title available?)
• A More Effective Linear Kernelization for Cluster Editing
• Algorithms for maximum independent sets
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Computing and Combinatorics
• Efficient Parameterized Preprocessing for Cluster Editing
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• Enumerating maximal independent sets with applications to graph colouring.
• Finding a Maximum Independent Set
• Finding odd cycle transversals.
• Fixed-Parameter Algorithms for Cluster Vertex Deletion
• Fourier meets M\"{o}bius: fast subset convolution
• Measure and conquer
• On cliques in graphs
• On generating all maximal independent sets
• Parameterized Algorithms for Hitting Set: The Weighted Case
• The Cluster Editing Problem: Implementations and Experiments
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(7)

• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Fixed-parameter algorithms for cluster vertex deletion
• scientific article; zbMATH DE number 975330 (Why is no real title available?)
• Optimal data compression algorithm
• Iterative polynomial interpolation and data compression
• Fixed-parameter tractability results for feedback set problems in tournaments
• Iterative compression and exact algorithms

This page was built for publication: Iterative Compression and Exact Algorithms

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