Iterative Compression for Exactly Solving NP-Hard Minimization Problems

DOI10.1007/978-3-642-02094-0_4zbMath1248.68380OpenAlexW2134628243MaRDI QIDQ3637312

Jiong Guo, Hannes Moser, Rolf Niedermeier

Publication date: 9 July 2009

Published in: Algorithmics of Large and Complex Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02094-0_4

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Studies in Computational Aspects of Voting, Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes, Parameterized complexity of vertex deletion into perfect graph classes, Separator-based data reduction for signed graph balancing, Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion, FPT algorithms for path-transversal and cycle-transversal problems, Confronting intractability via parameters, A fixed-parameter algorithm for the vertex cover \(P_3\) problem, Fixed-parameter tractability results for feedback set problems in tournaments, Fixed-parameter algorithms for cluster vertex deletion, Measuring Indifference: Unit Interval Vertex Deletion, A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems, Parameterized Complexity of Vertex Deletion into Perfect Graph Classes, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Correlation clustering
• Finding odd cycle transversals.
• Graph-modeled data clustering: Exact algorithms for clique generation
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Approximating minimum feedback sets and multicuts in directed graphs
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• Maximal Flow Through a Network
• Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
• Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$
• Parameterized Complexity and Approximability of the SLCS Problem
• Fixed-Parameter Algorithms for Kemeny Scores
• Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
• Chordal Deletion Is Fixed-Parameter Tractable
• A Cubic Kernel for Feedback Vertex Set
• Iterative Compression and Exact Algorithms
• Improved Algorithms for the Feedback Vertex Set Problems
• An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• ON DISJOINT CYCLES
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Faster Scaling Algorithms for Network Problems
• Multiway cuts in node weighted graphs
• Analogs & duals of the MAST problem for sequences & trees
• Parameterized and Exact Computation
• The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
• Optimal Edge Deletions for Signed Graph Balancing
• On the Hardness of Reoptimization
• Fixed-Parameter Algorithms for Cluster Vertex Deletion
• Experimental and Efficient Algorithms