Analogs & duals of the MAST problem for sequences & trees

DOI10.1016/S0196-6774(03)00081-6zbMath1064.68044OpenAlexW1970865484WikidataQ57360025 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

zbMATH Keywords

fixed-parameter tractability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (12)

Parameterized algorithms for feedback set problems and their duals in tournaments ⋮ The Impact of Parameterized Complexity to Interdisciplinary Problem Solving ⋮ Parameterized Complexity and Approximability of the SLCS Problem ⋮ A Survey on the Complexity of Flood-Filling Games ⋮ On the parameterized complexity of the multi-MCT and multi-MCST problems ⋮ On encodings of phylogenetic networks of bounded level ⋮ Parameterized complexity and approximability of the longest compatible sequence problem ⋮ Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number ⋮ Complexity issues in vertex-colored graph pattern matching ⋮ Iterative Compression for Exactly Solving NP-Hard Minimization Problems ⋮ On the space and circuit complexity of parameterized problems: classes and completeness ⋮ Tractability and hardness of flood-filling games on trees

This page was built for publication: Analogs & duals of the MAST problem for sequences & trees