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)
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Looking at the stars, A Fast Approximation Scheme for the Multiple Knapsack Problem, Win-win kernelization for degree sequence completion problems, Parameterizing edge modification problems above lower bounds, Parameterized Power Vertex Cover, A \(2k\)-kernelization algorithm for vertex cover based on crown decomposition, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Exact algorithms and applications for tree-like Weighted Set Cover, Preprocessing to reduce the search space: antler structures for feedback vertex set, Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters, What Is Known About Vertex Cover Kernelization?, Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack, The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT, Subexponential parameterized algorithms, Crown reductions for the minimum weighted vertex cover problem, Faster fixed-parameter tractable algorithms for matching and packing problems, Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable, Improved upper bounds for vertex cover, Kernels for packing and covering problems, Linear kernelizations for restricted 3-Hitting Set problems, Fixed-parameter tractability and data reduction for multicut in trees, The complexity ecology of parameters: An illustration using bounded max leaf number, Structural Properties of Hard Metric TSP Inputs, The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT, A fixed-parameter tractability result for multicommodity demand flow in trees, Parameterized computation and complexity: a new approach dealing with NP-hardness, A \(5k\)-vertex kernel for \(P_2\)-packing
