Exact exponential algorithms.
From MaRDI portal
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01)
Recommendations
- An introduction to exponential time exact algorithms for solving NP-hard problems
- scientific article; zbMATH DE number 1953201
- Exact algorithms for difficult graph problems
- Exact Algorithms for Generalized Combinatorial Optimization Problems
- Faster exact algorithms for hard problems: A parameterized point of view
Cited in
(only showing first 100 items - show all)- Minimal dominating sets in graph classes: combinatorial bounds and enumeration
- Exact algorithms for dominating induced matching based on graph partition
- Minimal dominating sets in graph classes: combinatorial bounds and enumeration
- Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
- 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
- Inclusion/exclusion meets measure and conquer
- Fast exact algorithm for \(L(2,1)\)-labeling of graphs
- Parameterized measure \& conquer for problems with no small kernels
- A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
- On an extension of the Sort \& Search method with application to scheduling theory
- Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
- Minimal dominating sets in interval graphs and trees
- Treewidth and pathwidth parameterized by the vertex cover number
- scientific article; zbMATH DE number 1953201 (Why is no real title available?)
- Bicolored independent sets and bicliques
- A note on the eternal dominating set problem
- Exact algorithms for Kayles
- Enumeration of minimal connected dominating sets for chordal graphs
- Enumerating minimal connected dominating sets in graphs of bounded chordality
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
- Exact algorithms for difficult graph problems
- On optimal approximability results for computing the strong metric dimension
- Parameterized algorithms and kernels for almost induced matching
- Improved parameterized algorithms and kernels for mixed domination
- Enumeration and maximum number of minimal dominating sets for chordal graphs
- On the number of minimal separators in graphs
- An exact algorithm for minimum distortion embedding
- Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
- Counting Maximal Independent Sets in Subcubic Graphs
- Bounding the running time of algorithms for scheduling and packing problems
- An improved exact algorithm for TSP in graphs of maximum degree 4
- A fast branching algorithm for cluster vertex deletion
- Exact algorithms for intervalizing coloured graphs
- End-vertices of graph search algorithms
- Enumerating minimal dominating sets in chordal graphs
- A measure and conquer approach for the parameterized bounded degree-one vertex deletion
- Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs
- An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs
- Fast exact algorithm for \(L(2,1)\)-labeling of graphs
- A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
- Computing the differential of a graph: hardness, approximability and exact algorithms
- Subset feedback vertex sets in chordal graphs
- Enumerating minimal subset feedback vertex sets
- An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set}
- Sharp separation and applications to exact and parameterized algorithms
- On the parameterised complexity of string morphism problems
- On the number of minimal dominating sets on some graph classes
- An exact algorithm for the maximum leaf spanning tree problem
- On computing the minimum 3-path vertex cover and dissociation number of graphs
- On finding optimal polytrees
- Largest chordal and interval subgraphs faster than \(2^n\)
- Algorithms and almost tight results for 3-colorability of small diameter graphs
- Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
- Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
- Parameterized algorithms for non-separating trees and branchings in digraphs
- On the parameterized complexity of b-\textsc{chromatic number}
- An exact exponential-time algorithm for the directed maximum leaf spanning tree problem
- Treewidth computation and extremal combinatorics
- A faster algorithm for dominating set analyzed by the potential method
- An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem
- Fixed-parameter algorithms for Vertex Cover \(P_3\)
- Computing directed pathwidth in \(O(1.89^n)\) time
- A refined algorithm for maximum independent set in degree-4 graphs
- Exact algorithms for Kayles
- A parameterized algorithm for bounded-degree vertex deletion
- Guarantees and limits of preprocessing in constraint satisfaction and reasoning
- An improved upper bound for SAT
- Large Induced Subgraphs via Triangulations and CMSO
- Lower bounds for the graph homomorphism problem
- Capacitated domination faster than \(O(2^n)\)
- Exponential upper bounds for the runtime of randomized search heuristics
- Exact algorithms for maximum induced matching
- Exact algorithms for scheduling programs with shared tasks
- Problems on finite automata and the exponential time hypothesis
- When polynomial approximation meets exact computation
- A simple and improved parameterized algorithm for bicluster editing
- A fast approximation algorithm for the maximum 2-packing set problem on planar graphs
- Algorithmic analysis of priority-based bin packing
- Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
- Moderately exponential time algorithms for the maximum bounded-degree-1 set problem
- Enumeration of maximal irredundant sets for claw-free graphs
- Parameterized approximation via fidelity preserving transformations
- Enumeration of maximal irredundant sets for claw-free graphs
- On the power of simple reductions for the maximum independent set problem
- Improved algorithms for the general exact satisfiability problem
- Exponential-time quantum algorithms for graph coloring problems
- Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
- Boundary classes for graph problems involving non-local properties
- Structural parameterizations of budgeted graph coloring
- On the complexity of broadcast domination and multipacking in digraphs
- Improved analysis of highest-degree branching for feedback vertex set
- Partition into triangles on bounded degree graphs
- Review on nature-inspired algorithms
- Faster algorithms for counting subgraphs in sparse graphs
- Edge bipartization faster than \(2^k\)
- An exact algorithm for maximum independent set in degree-5 graphs
- Algorithms solving the matching cut problem
- Faster FPT algorithm for 5-path vertex cover
This page was built for publication: Exact exponential algorithms.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q606873)
