Analogs & duals of the MAST problem for sequences & trees
From MaRDI portal
Publication:4820910
DOI10.1016/S0196-6774(03)00081-6zbMath1064.68044WikidataQ57360025 ScholiaQ57360025MaRDI QIDQ4820910
Michael T. Hallett, Michael R. Fellows, Ulrike Stege
Publication date: 1 October 2004
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0196-6774(03)00081-6
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
A Survey on the Complexity of Flood-Filling Games, On encodings of phylogenetic networks of bounded level, Parameterized complexity and approximability of the longest compatible sequence problem, Complexity issues in vertex-colored graph pattern matching, On the parameterized complexity of the multi-MCT and multi-MCST problems, Parameterized algorithms for feedback set problems and their duals in tournaments, Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number, On the space and circuit complexity of parameterized problems: classes and completeness, Tractability and hardness of flood-filling games on trees, The Impact of Parameterized Complexity to Interdisciplinary Problem Solving, Parameterized Complexity and Approximability of the SLCS Problem, Iterative Compression for Exactly Solving NP-Hard Minimization Problems
