Exact exponential algorithms.
From MaRDI portal
Publication:606873
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
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 (only showing first 100 items - show all)
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 ⋮ Advice complexity of adaptive priority algorithms
This page was built for publication: Exact exponential algorithms.
