Graph-Theoretic Concepts in Computer Science
From MaRDI portal
Publication:5902506
DOI10.1007/b93953zbMath1255.68113MaRDI QIDQ5902506
Publication date: 12 January 2010
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Win-win kernelization for degree sequence completion problems, The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT, Subexponential parameterized algorithms, Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack, Improved upper bounds for vertex cover, The complexity ecology of parameters: An illustration using bounded max leaf number, Looking at the stars, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Exact algorithms and applications for tree-like Weighted Set Cover, Faster fixed-parameter tractable algorithms for matching and packing problems, Linear kernelizations for restricted 3-Hitting Set problems, A fixed-parameter tractability result for multicommodity demand flow in trees, Parameterizing edge modification problems above lower bounds, Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable, Crown reductions for the minimum weighted vertex cover problem, Parameterized computation and complexity: a new approach dealing with NP-hardness, A Fast Approximation Scheme for the Multiple Knapsack Problem, Structural Properties of Hard Metric TSP Inputs, Parameterized Power Vertex Cover, Fixed-parameter tractability and data reduction for multicut in trees, Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters, The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT