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 (only showing first 100 items - show all)

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

This page was built for publication: