scientific article; zbMATH DE number 751135
From MaRDI portal
Publication:4764626
zbMath0817.68082MaRDI QIDQ4764626
Publication date: 4 May 1995
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (27)
Near-optimal nonapproximability results for some \textsc{Npo} PB-complete problems ⋮ Matrix sparsification and the sparse null space problem ⋮ Finding disjoint paths with related path costs ⋮ Analyzing the reachability problem in choice networks ⋮ On the analysis of optimization problems in arc-dependent networks ⋮ Kernel bounds for path and cycle problems ⋮ Analyzing read-once cutting plane proofs in Horn systems ⋮ Structure in approximation classes ⋮ On the approximability of path and cycle problems in arc-dependent networks ⋮ Reachability in choice networks ⋮ Approximating Alternative Solutions ⋮ Optimal length cutting plane refutations of integer programs ⋮ Unit read-once refutations for systems of difference constraints ⋮ Paths, trees and matchings under disjunctive constraints ⋮ A survey on the structure of approximation classes ⋮ The complexity of makespan minimization for pipeline transportation. ⋮ On approximability of linear ordering and related NP-optimization problems on graphs. ⋮ A quantum walk-assisted approximate algorithm for bounded NP optimisation problems ⋮ Scheduling on parallel machines with preemption and transportation delays ⋮ On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem ⋮ Analyzing unit read-once refutations in difference constraint systems ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances ⋮ On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems ⋮ Some APX-completeness results for cubic graphs ⋮ Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas ⋮ Minimal distance of propositional models ⋮ Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights
This page was built for publication:
