scientific article; zbMATH DE number 1507224

Michael R. Fellows, Rodney G. Downey

Publication date: 17 January 2001

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On miniaturized problems in parameterized complexity theory, The Turing way to parameterized complexity, A fixed-parameter algorithm for minimum quartet inconsistency, On the existence of subexponential parameterized algorithms, Graph separators: A parameterized view, Improved exact algorithms for MAX-SAT, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Threes!, Fives, 1024!, and 2048 are hard, Computing the similarity of two sequences with nested arc annotations, An existential locality theorem, Computing crossing numbers in quadratic time, Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability, On the optimality of exact and approximation algorithms for scheduling problems, Streaming deletion problems parameterized by vertex cover, Scattered packings of cycles, Leaf realization problem, caterpillar graphs and prefix normal words, Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control, Parameterized complexity of the list coloring reconfiguration problem with graph parameters, A \(2k\)-kernelization algorithm for vertex cover based on crown decomposition, The \(S\)-\textsc{labeling} problem: an algorithmic tour, From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability, On product covering in 3-tier supply chain models: natural complete problems for W[3 and W[4]], Polynomial time approximation schemes and parameterized complexity, An efficient fixed-parameter algorithm for 3-hitting set, The parameterized complexity of local search for TSP, more refined, Relativization makes contradictions harder for resolution, Infeasibility of instance compression and succinct PCPs for NP, Variants of constrained longest common subsequence, Aspects of a multivariate complexity analysis for rectangle tiling, On the complexity of the regenerator location problem treewidth and other parameters, Fixed-parameter tractability of disjunction-free default reasoning, On the parameterized complexity of the repetition free longest common subsequence problem, Identification of function distinguishable languages., On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\), On the model-checking of monadic second-order formulas with edge set quantifications, Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules, Kernelization for cycle transversal problems, New results for the longest haplotype reconstruction problem, Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT., Parameterized random complexity, Fast evaluation of interlace polynomials on graphs of bounded treewidth, Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem, Multicut in trees viewed through the eyes of vertex cover, Parameterized proof complexity, Algorithms for graphs with small octopus, Betweenness parameterized above tight lower bound, Book review of: Rolf Niedermeier, Invitation to fixed-parameter algorithms, Dominating set is fixed parameter tractable in claw-free graphs, Confronting intractability via parameters, On the induced matching problem, Complexity of splits reconstruction for low-degree trees, Approximation algorithms for intersection graphs, The kernelization complexity of connected domination in graphs with (no) small cycles, Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable, Seeing the trees and their branches in the network is hard, Towards optimal and expressive kernelization for \(d\)-hitting set, Tractabilities and intractabilities on geometric intersection graphs, Pattern-guided \(k\)-anonymity, Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions, Complexity of fixed-size bit-vector logics, An improved FPT algorithm for almost forest deletion problem, Incremental problems in the parameterized complexity setting, On compatibility and incompatibility of collections of unrooted phylogenetic trees, Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number, Fly-automata for checking \(\mathrm{MSO}_2\) graph properties, Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs, An FPT algorithm for planar multicuts with sources and sinks on the outer face, Graph editing problems with extended regularity constraints, On making a distinguished vertex of minimum degree by vertex deletion, Fixed-parameter tractability of satisfying beyond the number of variables, Every minor-closed property of sparse graphs is testable, An improved lower bound on approximation algorithms for the closest substring problem, Improved deterministic algorithms for weighted matching and packing problems, Linear delay enumeration and monadic second-order logic, An updated survey on the linear ordering problem for weighted or unweighted tournaments, Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable, \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth, On the small cycle transversal of planar graphs, Minimum vertex cover in rectangle graphs, Finding common structured patterns in linear graphs, Improved upper bounds for vertex cover, New results on optimizing rooted triplets consistency, Generalizations of matched CNF formulas, Upper and lower bounds for finding connected motifs in vertex-colored graphs, Boolean-width of graphs, On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering, On the parameterized complexity of multiple-interval graph problems, A more effective linear kernelization for cluster editing, On the pseudo-achromatic number problem, Learning large-alphabet and analog circuits with value injection queries, On the treewidth of dynamic graphs, Induced disjoint paths in AT-free graphs, Parameterized complexity of vertex colouring, The complexity of finding temporal separators under waiting time constraints, Graph operations characterizing rank-width, Orthogonal planarity testing of bounded treewidth graphs, Complexity of abstract argumentation under a claim-centric view, EPTAS for load balancing problem on parallel machines with a non-renewable resource, Parameterized complexity of finding subgraphs with hereditary properties., Fixed-parameter complexity in AI and nonmonotonic reasoning, Decremental Optimization of Dominating Sets Under the Reconfiguration Framework, A Parameterized Perspective on Attacking and Defending Elections, Parameterized Analysis of Art Gallery and Terrain Guarding, Tandem Duplications, Segmental Duplications and Deletions, and Their Applications, Collaborating with Hans: Some Remaining Wonderments, Algorithms, Complexity, and Hans, As Time Goes By: Reflections on Treewidth for Temporal Graphs, Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds, A Retrospective on (Meta) Kernelization, Some notes on bounded starwidth graphs, Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG, Complexity results for rainbow matchings, Genus characterizes the complexity of certain graph problems: Some tight results, Unnamed Item, Algorithmic Aspect of Minus Domination on Small-Degree Graphs, Unnamed Item, A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion, Parameterized complexity classes beyond para-NP, Complexity of edge monitoring on some graph classes, Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem, Tractability, hardness, and kernelization lower bound for and/or graph solution, Parameterized complexity of distance labeling and uniform channel assignment problems, A unified framework for designing EPTAS for load balancing on parallel machines, Algorithms for Propositional Model Counting, Improved Algorithms for Bicluster Editing, Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems, Fixed Structure Complexity, New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem, Capacitated Domination and Covering: A Parameterized Perspective, A Purely Democratic Characterization of W[1], Parameterized Complexity and Approximability of the SLCS Problem, FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs, Improved kernels for tracking paths, Parameterized Algorithms and Hardness Results for Some Graph Motif Problems, Constraint Bipartite Vertex Cover Simpler Exact Algorithms and Implementations, The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants, Improved PTAS for the constrained \(k\)-means problem, Segmenting Strings Homogeneously Via Trees, Obtaining a Planar Graph by Vertex Deletion, Fixed-Parameter Algorithms for Kemeny Scores, Facility Location Problems: A Parameterized View, Minimum Leaf Out-Branching Problems, Parameterized Computational Complexity of Dodgson and Young Elections, Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs, An \(O^{*}(3.53^{3k})\)-time parameterized algorithm for the 3-set packing problem, Tractable cases of the extended global cardinality constraint, Unnamed Item, Unnamed Item, Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey, Unnamed Item, Parameterized domination in circle graphs, A cubic-vertex kernel for flip consensus tree, Unnamed Item, Rationalizations of Condorcet-consistent rules via distances of Hamming type, Faster Steiner Tree Computation in Polynomial-Space, Tight bounds for parameterized complexity of cluster editing with a small number of clusters, Genomic Scaffold Filling: A Progress Report, Finding Disjoint Dense Clubs in an Undirected Graph, On the Fixed-Parameter Tractability of Some Matching Problems Under the Color-Spanning Model, The Complexity of Finding (Approximate Sized) Distance-d Dominating Set in Tournaments, On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs, Constant thresholds can make target set selection tractable, Minimum fill-in of sparse graphs: kernelization and approximation, Colored hypergraph isomorphism is fixed parameter tractable, An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints, Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable, Clustering with Partial Information, Monadic Second Order Logic on Graphs with Local Cardinality Constraints, Unnamed Item, Algorithms and Complexity of Power Domination in Graphs, Hybridization Number on Three Rooted Binary Trees is EPT, Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs, Computational aspects of optimal strategic network diffusion, Bidimensionality and Kernels, Distance-Based Clique Relaxations in Networks: s-Clique and s-Club, Fine-Grained Complexity Theory (Tutorial), FPT-algorithm for computing the width of a simplex given by a convex hull, Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers, Parameterized Complexity, Kernelization: New Upper and Lower Bound Techniques, Planar Capacitated Dominating Set Is W[1-Hard], On Finding Directed Trees with Many Leaves, Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms, Pareto Complexity of Two-Parameter FPT Problems: A Case Study for Partial Vertex Cover, Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms, Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs, A Probabilistic Approach to Problems Parameterized above or below Tight Bounds, Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor, On the Directed Degree-Preserving Spanning Tree Problem, Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters, Backdoors to tractable answer set programming, Structural tractability of enumerating CSP solutions, Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits, On the average-case complexity of parameterized clique, Modifying a graph using vertex elimination, Parameterized analysis of paging and list update algorithms, Using patterns to form homogeneous teams, A characterisation of clique-width through nested partitions, Faster parameterized algorithms for deletion to split graphs, Unifying known lower bounds via geometric complexity theory, Backdoors to Normality for Disjunctive Logic Programs, Cluster Editing, \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions, Parameterized complexity of perfectly matched sets, Problems hard for treewidth but easy for stable gonality, Edge-treewidth: algorithmic and combinatorial properties, A parameterized algorithm for subset feedback vertex set in tournaments, Minimum <scp>color‐degree</scp> perfect b‐matchings, Parameterized complexity of path set packing, Parameterised counting in logspace, Finding \(k\)-secluded trees faster, On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts, On the parameterized complexity of s-club cluster deletion problems, The \textsc{Red-Blue Separation} problem on graphs, Perfect domination and small cycles, Unnamed Item, Parameterized Complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs, A CNF Formula Hierarchy over the Hypercube, Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs, Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs, Voting Procedures, Complexity of, Diverse Pairs of Matchings, Parameterized Complexity of Graph Burning, Fixed-Parameter Algorithms for Finding Agreement Supertrees, Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality, Simple Geometrical Intersection Graphs, Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs, Bandwidth of Bipartite Permutation Graphs in Polynomial Time, Better Algorithms and Bounds for Directed Maximum Leaf Problems, Covering Graphs with Few Complete Bipartite Subgraphs, Exploring the gap between treedepth and vertex cover through vertex integrity, Approximability of covering cells with line segments, Lossy Kernels for Connected Dominating Set on Sparse Graphs, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Parameterized Graph Editing with Chosen Vertex Degrees, Multiple Hypernode Hitting Sets and Smallest Two-Cores with Targets, Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems, Parameterized Algorithms for Generalized Domination, Enumerating Isolated Cliques in Synthetic and Financial Networks, Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices, Calculation of Discrepancy Measures and Applications, A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs