Exact exponential algorithms.

DOI10.1007/978-3-642-16533-7zbMath1370.68002OpenAlexW2015963099MaRDI QIDQ606873

Dieter Kratsch, Fedor V. Fomin

Publication date: 18 November 2010

Published in: Texts in Theoretical Computer Science. An EATCS Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16533-7

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Nonnumerical algorithms (68W05) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

An improved upper bound for SAT ⋮ Enumerating minimal connected dominating sets in graphs of bounded chordality ⋮ Algorithmic analysis of priority-based bin packing ⋮ Moderately exponential time algorithms for the maximum bounded-degree-1 set problem ⋮ Enumeration of maximal irredundant sets for claw-free graphs ⋮ An improved deterministic parameterized algorithm for cactus vertex deletion ⋮ A fast algorithm for permutation pattern matching based on alternating runs ⋮ Computing directed pathwidth in \(O(1.89^n)\) time ⋮ An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs ⋮ Parameterizing edge modification problems above lower bounds ⋮ On the parameterised complexity of string morphism problems ⋮ Largest chordal and interval subgraphs faster than \(2^n\) ⋮ Parameterized algorithms for non-separating trees and branchings in digraphs ⋮ Exact algorithms for scheduling programs with shared tasks ⋮ On the parameterized complexity of b-\textsc{chromatic number} ⋮ Treewidth and pathwidth parameterized by the vertex cover number ⋮ Minimal dominating sets in interval graphs and trees ⋮ Problems on finite automata and the exponential time hypothesis ⋮ Real-valued group testing for quantitative molecular assays ⋮ Enumeration of minimal connected dominating sets for chordal graphs ⋮ Enumeration and maximum number of minimal connected vertex covers in graphs ⋮ Minimal dominating sets in graph classes: combinatorial bounds and enumeration ⋮ A refined algorithm for maximum independent set in degree-4 graphs ⋮ On an extension of the Sort \& Search method with application to scheduling theory ⋮ A novel parameterised approximation algorithm for \textsc{minimum vertex cover} ⋮ Fast exact algorithm for \(L(2,1)\)-labeling of graphs ⋮ Parameterized approximation via fidelity preserving transformations ⋮ Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms ⋮ Parameterized complexity of happy coloring problems ⋮ An exact algorithm for maximum independent set in degree-5 graphs ⋮ Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms ⋮ Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ Algorithms solving the matching cut problem ⋮ Capacitated domination faster than \(O(2^n)\) ⋮ Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack ⋮ Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket ⋮ Bicolored independent sets and bicliques ⋮ Parameterized algorithms and kernels for almost induced matching ⋮ Fixing balanced knockout and double elimination tournaments ⋮ An exact exponential-time algorithm for the directed maximum leaf spanning tree problem ⋮ On computing the minimum 3-path vertex cover and dissociation number of graphs ⋮ Guarantees and limits of preprocessing in constraint satisfaction and reasoning ⋮ An exact algorithm for the maximum leaf spanning tree problem ⋮ Exponential upper bounds for the runtime of randomized search heuristics ⋮ Enumerating minimal subset feedback vertex sets ⋮ Exact algorithms for Kayles ⋮ On the number of minimal dominating sets on some graph classes ⋮ Solving the 2-disjoint connected subgraphs problem faster than \(2^n\) ⋮ Edge bipartization faster than \(2^k\) ⋮ Improved algorithms for the general exact satisfiability problem ⋮ A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP ⋮ Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions ⋮ On the complexity of broadcast domination and multipacking In digraphs ⋮ Parameterized algorithms and kernels for rainbow matching ⋮ On the tractability of \(( k , i )\)-coloring ⋮ Faster exponential-time algorithms for approximately counting independent sets ⋮ Review on nature-inspired algorithms ⋮ Refined notions of parameterized enumeration kernels with applications to matching cut enumeration ⋮ On finding optimal polytrees ⋮ Exact exponential algorithms for 3-machine flowshop scheduling problems ⋮ Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems ⋮ On optimal approximability results for computing the strong metric dimension ⋮ Fixed-parameter algorithms for Vertex Cover \(P_3\) ⋮ Exact algorithms for minimum weighted dominating induced matching ⋮ Inclusion/exclusion meets measure and conquer ⋮ Scheduling partially ordered jobs faster than \(2^n\) ⋮ Parameterized measure \& conquer for problems with no small kernels ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ An exact algorithm for minimum distortion embedding ⋮ Exact algorithms for maximum independent set ⋮ Computing maximum \(k\)-defective cliques in massive graphs ⋮ \textit{Branch} \& \textit{Memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees ⋮ Stable matching games: manipulation via subgraph isomorphism ⋮ An exact exponential branch-and-merge algorithm for the single machine total tardiness problem ⋮ Analyzing clustering and partitioning problems in selected VLSI models ⋮ Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization ⋮ A note on the eternal dominating set problem ⋮ Improved analysis of highest-degree branching for feedback vertex set ⋮ Faster algorithms for counting subgraphs in sparse graphs ⋮ Enumerating minimal dominating sets in chordal graphs ⋮ Many-visits TSP revisited ⋮ An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses ⋮ Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights ⋮ A simple and improved parameterized algorithm for bicluster editing ⋮ Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas ⋮ Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations ⋮ Exact algorithms for counting 3-colorings of graphs ⋮ On zero-error codes produced by greedy algorithms ⋮ Dual parameterization of weighted coloring ⋮ Worst-case analysis of clique MIPs ⋮ Polynomial kernels for tracking shortest paths ⋮ Moderate exponential-time algorithms for scheduling problems ⋮ An improved exact algorithm for TSP in graphs of maximum degree 4 ⋮ Exact algorithms for intervalizing coloured graphs ⋮ A fast branching algorithm for cluster vertex deletion ⋮ Algorithms and almost tight results for 3-colorability of small diameter graphs ⋮ Projection heuristics for binary branchings between sum and product ⋮ A fast algorithm for SAT in terms of formula length ⋮ A refined branching algorithm for the maximum satisfiability problem ⋮ An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure ⋮ Advice complexity of adaptive priority algorithms ⋮ Finding perfect matching cuts faster ⋮ Priority-based bin packing with subset constraints ⋮ Faster exact algorithms for some terminal set problems ⋮ Destroying Bicolored $P_3$s by Deleting Few Edges ⋮ Enumeration of Maximal Irredundant Sets for Claw-Free Graphs ⋮ Ordering a Sparse Graph to Minimize the Sum of Right Ends of Edges ⋮ A Faster Algorithm for Dominating Set Analyzed by the Potential Method ⋮ Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration ⋮ Counting Maximal Independent Sets in Subcubic Graphs ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ A Survey on Spanning Tree Congestion ⋮ Lower Bounds for the Graph Homomorphism Problem ⋮ What Circuit Classes Can Be Learned with Non-Trivial Savings? ⋮ Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ Almost Induced Matching: Linear Kernels and Parameterized Algorithms ⋮ Treewidth computation and extremal combinatorics ⋮ Partition into triangles on bounded degree graphs ⋮ Colorings with few colors: counting, enumeration and combinatorial bounds ⋮ A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion ⋮ Finding near-optimal independent sets at scale ⋮ Boundary classes for graph problems involving non-local properties ⋮ Exact algorithms for maximum induced matching ⋮ Parameterized complexity of secluded connectivity problems ⋮ Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size ⋮ Algorithms Solving the Matching Cut Problem ⋮ End-Vertices of Graph Search Algorithms ⋮ Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ⋮ Enumeration of minimal tropical connected sets ⋮ Further improvements for SAT in terms of formula length ⋮ Super-polynomial approximation branching algorithms ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics ⋮ Moderate worst-case complexity bounds for the permutation flowshop scheduling problem using inclusion-exclusion ⋮ Reachability in choice networks ⋮ A fast approximation algorithm for the maximum 2-packing set problem on planar graphs ⋮ Analyzing the 3-path vertex cover problem in planar bipartite graphs ⋮ Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation ⋮ Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm ⋮ Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework ⋮ A Polynomial-Space Exact Algorithm for TSP in Degree-6 Graphs ⋮ Solving target set selection with bounded thresholds faster than \(2^n\) ⋮ Dominator coloring and CD coloring in almost cluster graphs ⋮ Algorithms for 2-club cluster deletion problems using automated generation of branching rules ⋮ Convex Characters, Algorithms, and Matchings ⋮ Two generalizations of proper coloring: hardness and approximability ⋮ An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set} ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Unnamed Item ⋮ Graph Motif Problems Parameterized by Dual ⋮ Enumerating Minimal Tropical Connected Sets ⋮ Exact and Parameterized Algorithms for (k, i)-Coloring ⋮ Subset feedback vertex sets in chordal graphs ⋮ When polynomial approximation meets exact computation ⋮ Exact algorithms for problems related to the densest \(k\)-set problem ⋮ Computing the differential of a graph: hardness, approximability and exact algorithms ⋮ Kernelization and Parameterized Algorithms for 3-Path Vertex Cover ⋮ Tight bounds for parameterized complexity of cluster editing with a small number of clusters ⋮ Dual parameterization of Weighted Coloring ⋮ Solving Target Set Selection with Bounded Thresholds Faster than 2^n ⋮ Fast Exact Algorithm for L(2,1)-Labeling of Graphs ⋮ Invitation to Algorithmic Uses of Inclusion–Exclusion ⋮ When polynomial approximation meets exact computation ⋮ Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs ⋮ Strong triadic closure in cographs and graphs of low maximum degree ⋮ Below All Subsets for Minimal Connected Dominating Set ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems ⋮ Parameterized algorithms for module map problems ⋮ Enumeration and maximum number of maximal irredundant sets for chordal graphs ⋮ Bounding the Running Time of Algorithms for Scheduling and Packing Problems ⋮ Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem ⋮ Parameterized Complexity of Conflict-Free Graph Coloring ⋮ Structural parameterizations of budgeted graph coloring ⋮ The perfect matching cut problem revisited ⋮ Subset feedback vertex set in chordal and split graphs ⋮ Structural parameterizations of budgeted graph coloring ⋮ The perfect matching cut problem revisited ⋮ Computing exact clustering posteriors with subset convolution ⋮ A Parameterized Algorithm for Bounded-Degree Vertex Deletion ⋮ On the Power of Simple Reductions for the Maximum Independent Set Problem ⋮ Matching cut in graphs with large minimum degree ⋮ Unnamed Item ⋮ Faster graph coloring in polynomial space ⋮ Improved parameterized algorithms and kernels for mixed domination ⋮ On the Number of Minimal Separators in Graphs ⋮ Enumeration and maximum number of minimal dominating sets for chordal graphs ⋮ Exact Algorithms for Kayles ⋮ Revisiting connected vertex cover: FPT algorithms and lossy kernels ⋮ Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem ⋮ Parameterized Algorithms and Kernels for Rainbow Matching ⋮ Basic Terminology, Notation and Results ⋮ Unnamed Item ⋮ Exponential-time quantum algorithms for graph coloring problems ⋮ Towards an algorithmic guide to Spiral Galaxies ⋮ Moderately exponential time and fixed parameter approximation algorithms ⋮ An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem ⋮ Exact algorithms for dominating induced matching based on graph partition ⋮ Moderately exponential time algorithms for the maximum induced matching problem