scientific article; zbMATH DE number 1341905
From MaRDI portal
Publication:4263467
zbMath0935.68046MaRDI QIDQ4263467
Michael R. Fellows, Ulrike Stege, Rodney G. Downey
Publication date: 4 May 2000
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Philosophical and critical aspects of logic and foundations (03A05) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (58)
Parameterized enumeration, transversals, and imperfect phylogeny reconstruction ⋮ Moving policies in cyclic assembly line scheduling ⋮ Looking at the stars ⋮ Possible winner problems on partial tournaments: a parameterized study ⋮ Tractability in constraint satisfaction problems: a survey ⋮ Solving large FPT problems on coarse-grained parallel machines ⋮ A fixed-parameter algorithm for minimum quartet inconsistency ⋮ On the existence of subexponential parameterized algorithms ⋮ Improved exact algorithms for MAX-SAT ⋮ Refined memorization for vertex cover ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ The Birth and Early Years of Parameterized Complexity ⋮ The Impact of Parameterized Complexity to Interdisciplinary Problem Solving ⋮ A top-down approach to search-trees: Improved algorithmics for 3-hitting set ⋮ On the Pseudo-achromatic Number Problem ⋮ A fixed-parameter tractable algorithm for matrix domination ⋮ A multivariate framework for weighted FPT algorithms ⋮ Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter ⋮ An efficient fixed-parameter algorithm for 3-hitting set ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ Additive stabilizers for unstable graphs ⋮ Colouring a dominating set without conflicts: \(q\)-subset square colouring ⋮ A Purely Democratic Characterization of W[1] ⋮ Meta-kernelization with structural parameters ⋮ Identification of function distinguishable languages. ⋮ Editing graphs to satisfy degree constraints: a parameterized approach ⋮ Data reductions and combinatorial bounds for improved approximation algorithms ⋮ What Is Known About Vertex Cover Kernelization? ⋮ An exact algorithm for connected red-blue dominating set ⋮ Small vertex cover makes Petri net coverability and boundedness easier ⋮ Multicut in trees viewed through the eyes of vertex cover ⋮ Surfing with Rod ⋮ Book review of: Rolf Niedermeier, Invitation to fixed-parameter algorithms ⋮ Guarantees and limits of preprocessing in constraint satisfaction and reasoning ⋮ Confronting intractability via parameters ⋮ Is computational complexity a barrier to manipulation? ⋮ On the induced matching problem ⋮ Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms ⋮ The modular decomposition of countable graphs. Definition and construction in monadic second-order logic ⋮ Sources of complexity in subset choice ⋮ Kernels in planar digraphs ⋮ A problem reduction based approach to discrete optimization algorithm design ⋮ A parametric analysis of the state-explosion problem in model checking ⋮ Parameterized Complexity Results in Symmetry Breaking ⋮ On the pseudo-achromatic number problem ⋮ Parameterized Complexity Results for 1-safe Petri Nets ⋮ On parameterized exponential time complexity ⋮ Rank Vertex Cover as a Natural Problem for Algebraic Compression ⋮ Backdoors to planning ⋮ Parameterized Complexity ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ An exact algorithm for subgraph homeomorphism ⋮ Dynamic kernels for hitting sets and set packing ⋮ A refined search tree technique for dominating set on planar graphs ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ Backdoors to tractable answer set programming ⋮ A general method to speed up fixed-parameter-tractable algorithms ⋮ A complete parameterized complexity analysis of bounded planning
This page was built for publication:
