2005 · 117 citations · 38 references
Numerical AnalysisMathematical ProgrammingEngineeringNp Hard ProblemsAnalysis Of AlgorithmComputational ComplexityAlgorithm ImplementationAlgorithm DesignP Versus Np ProblemDiscrete MathematicsCombinatorial OptimizationApproximation TheoryComputer EngineeringNew TechniquesComputer ScienceExponential AlgorithmComputational ScienceGraph TheoryExponential Lower BoundsTime ComplexityComputational ProblemExponential Time
This survey concerns techniques in design and analysis of algo- rithms that can be used to solve NP hard problems faster than ex- haustive search algorithms (but still in exponential time). We discuss several of such techniques: Measure & Conquer, Exponential Lower Bounds, Bounded Tree-width, and Memorization. We also consider some extensions of the mentioned techniques to parameterized algo- rithms.
38
Graph minors. II. Algorithmic aspects of tree-width
Neil Robertson, Paul Seymour · Journal of Algorithms · 1986 · 1.5K citations