Faster exponential algorithms for cut problems via geometric data structures
From MaRDI portal
Cites work
- A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
- A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
- A new algorithm for optimal 2-constraint satisfaction and its implications
- A probabilistic algorithm for k-SAT and constraint satisfaction problems
- Algorithms for graphs of bounded treewidth via orthogonal range searching
- Asymptotically almost every \(2r\)-regular graph has an internal partition
- Branch and recharge: exact algorithms for generalized domination
- Computing Partitions with Applications to the Knapsack Problem
- Determinant sums for undirected Hamiltonicity
- Exact exponential algorithms for clustering problems
- Exact exponential algorithms.
- Faster exact algorithms for some terminal set problems
- Finding a Maximum Independent Set
- Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
- Graph decomposition with constraints on the connectivity and minimum degree
- scientific article; zbMATH DE number 944226 (Why is no real title available?)
- Title not available (Why is no real title available?)
- Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors
- Internal partitions of regular graphs
- Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
- On connections between k-coloring and Euclidean k-means
- ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
- On problems as hard as CNF-SAT
- On the complexity of k-SAT
- Open problems around exact algorithms
- Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
- Recognizing decomposable graphs
- Satisfactory graph partition, variants, and generalizations
- Scheduling partially ordered jobs faster than \(2^n\)
- Solving directed multiway cut faster than 2ⁿ
- Solving multicut faster than \(2^{n }\)
- Sort and Search: exact algorithms for generalized domination
- The complexity of the matching-cut problem for planar graphs and other graph classes
- The set cover conjecture and subgraph isomorphism with a tree pattern
Cited in
(1)- Engineering minimal \(k\)-perfect hash functions
This page was built for publication: Faster exponential algorithms for cut problems via geometric data structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7322527)
