scientific article; zbMATH DE number 1161563
From MaRDI portal
Publication:4393480
zbMath0914.68076MaRDI QIDQ4393480
Michael R. Fellows, Rodney G. Downey
Publication date: 10 June 1998
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (only showing first 100 items - show all)
Structural tractability of counting of solutions to conjunctive queries ⋮ Ranking chain sum orders ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Kernelizations for the hybridization number problem on multiple nonbinary trees ⋮ On the complexity of connection games ⋮ Solving linear equations parameterized by Hamming weight ⋮ Graph isomorphism parameterized by elimination distance to bounded degree ⋮ Fly-automata for checking monadic second-order properties of graphs of bounded tree-width ⋮ The Flood-It game parameterized by the vertex cover number ⋮ Kernelization using structural parameters on sparse graph classes ⋮ A generalization of Spira's theorem and circuits with small segregators or separators ⋮ Courcelle's theorem for triangulations ⋮ Towards more expressive ontology languages: the query answering problem ⋮ Increasing the minimum degree of a graph by contractions ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ Parameterized complexity of Min-power multicast problems in wireless ad hoc networks ⋮ Shuffled languages -- representation and recognition ⋮ Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ Finding approximate and constrained motifs in graphs ⋮ Detecting induced minors in AT-free graphs ⋮ Incremental list coloring of graphs, parameterized by conservation ⋮ Two-layer planarization parameterized by feedback edge set ⋮ Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems ⋮ Parameterized complexity of max-lifetime target coverage in wireless sensor networks ⋮ On the approximability of the link building problem ⋮ Maximum balanced subgraph problem parameterized above lower bound ⋮ Deciding the winner in \(k\) rounds for DISJOINT ARROWS, a new combinatorial partizan game ⋮ Parameterized complexity of \(k\)-Chinese postman problem ⋮ Improved linear problem kernel for planar connected dominating set ⋮ Parameterized maximum path coloring ⋮ Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems ⋮ Parameterized complexity of MaxSat above average ⋮ Data reduction for graph coloring problems ⋮ Polynomial kernels for proper interval completion and related problems ⋮ Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization ⋮ A new bound for 3-satisfiable MaxSat and its algorithmic application ⋮ Revisiting the complexity of and/or graph solution ⋮ Parameterized complexity of connected even/odd subgraph problems ⋮ The constrained shortest common supersequence problem ⋮ On the approximability of the exemplar adjacency number problem for genomes with gene repetitions ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ Towards NP-P via proof complexity and search ⋮ A parameterized algorithm for the hyperplane-cover problem ⋮ Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension ⋮ Parameterized complexity of finding small degree-constrained subgraphs ⋮ Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables ⋮ A three-string approach to the closest string problem ⋮ Editing graphs to satisfy degree constraints: a parameterized approach ⋮ On bounded block decomposition problems for under-specified systems of equations ⋮ On making directed graphs transitive ⋮ A structural/temporal query language for business processes ⋮ Parameterized complexity of generalized domination problems ⋮ A strengthened analysis of an algorithm for dominating set in planar graphs ⋮ On graph contractions and induced minors ⋮ Mod/Resc parsimony inference: theory and application ⋮ Phylogeny- and parsimony-based haplotype inference with constraints ⋮ Routing multi-class traffic flows in the plane ⋮ A note on the parameterized complexity of unordered maximum tree orientation ⋮ Influence of tree topology restrictions on the complexity of haplotyping with missing data ⋮ Most probable explanations in Bayesian networks: complexity and tractability ⋮ Parameterized Eulerian strong component arc deletion problem on tournaments ⋮ Local search: is brute-force avoidable? ⋮ Catalan structures and dynamic programming in \(H\)-minor-free graphs ⋮ Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem ⋮ Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number ⋮ On the parameterized complexity of coloring graphs in the absence of a linear forest ⋮ Graph-based data clustering with overlaps ⋮ Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover ⋮ Charge and reduce: A fixed-parameter algorithm for string-to-string correction ⋮ Parameterized complexity and approximability of the longest compatible sequence problem ⋮ FPT algorithms for path-transversal and cycle-transversal problems ⋮ Treewidth governs the complexity of target set selection ⋮ On the directed full degree spanning tree problem ⋮ Lower bounds on kernelization ⋮ Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search ⋮ Book review of: Rolf Niedermeier, Invitation to fixed-parameter algorithms ⋮ Subexponential parameterized algorithms ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ Guarantees and limits of preprocessing in constraint satisfaction and reasoning ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Independent dominating set problem revisited ⋮ Induced subgraph isomorphism on proper interval and bipartite permutation graphs ⋮ Combinatorics for smaller kernels: the differential of a graph ⋮ Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees ⋮ A fixed-parameter algorithm for the vertex cover \(P_3\) problem ⋮ Computing the pathwidth of directed graphs with small vertex cover ⋮ \(k\)-attribute-anonymity is hard even for \(k=2\) ⋮ Complexity of conflict-free colorings of graphs ⋮ Consequence-based and fixed-parameter tractable reasoning in description logics ⋮ Graphs with few \(P_4\)'s under the convexity of paths of order three ⋮ Correcting gene tree by removal and modification: tractability and approximability ⋮ A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization ⋮ Parameterized complexity analysis for the closest string with wildcards problem ⋮ Inapproximability results for graph convexity parameters ⋮ On the max min vertex cover problem ⋮ On finding optimal polytrees ⋮ Parameterized complexity of strip packing and minimum volume packing ⋮ On the complexity of computing the \(k\)-restricted edge-connectivity of a graph ⋮ Improved kernel results for some FPT problems based on simple observations ⋮ Crowns in bipartite graphs
This page was built for publication:
