Fixed-Parameter Tractability and Completeness II: On Completeness for W[1]

No abstract is available for this paper.

• Publication year

  1995

• Venue

  Theoretical Computer Science

• Publication date

  1995-04-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0304-3975(94)00097-3
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the parameterized complexity of short computation and factorization

  1997cited by this paper
• Parameterized Computational Feasibility

  1995cited by this paper
• Fixed-Parameter Tractability and Completeness IV: On Completeness for W[P] and PSPACE Analogues

  1995cited by this paper
• Graph Minors .XIII. The Disjoint Paths Problem

  1995cited by this paper
• The Parameterized Complexity of Sequence Alignment and Consensus

  1994cited by this paper
• The Parameterized Complexity of Some Problems in Logic and Linguistics

  1994cited by this paper
• Nondeterminism Within P

  1993cited by this paper
• Parameterized learning complexity

  1993cited by this paper
• On limited nondeterminism and the complexity of the V-C dimension

  1993cited by this paper
• Fixed-parameter tractability and completeness III: some structural aspects of the W hierarchy

  1993cited by this paper
• Fixed-Parameter Intractability II (Extended Abstract)

  1993cited by this paper
• Fixed-parameter intractability

  1992cited by this paper
• Fixed Parameter Tractability and Completeness III: Some Structural Aspects of the W Hierarchy

  1992cited by this paper
• On Disjoint Cycles

  1991cited by this paper
• Graph Algorithms

  1991cited by this paper
• Handbook of theoretical computer science - Part A: Algorithms and complexity; Part B: Formal models and semantics

  1990cited by this paper
• On search decision and the efficiency of polynomial-time algorithms

  1989cited by this paper
• An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations

  1989cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• Johnson: computers and intractability: a guide to the theory of np- completeness (freeman

  1979cited by this paper
• Computers and Intractability: A Guide to the Theory of NP-Completeness

  1979cited by this paper
• FIXED-PARAMETER TRACTABILITY AND COMPLETENESS

  year unknowncited by this paper

• Enumerating Cliques on k-Partite Graphs

  2026cites this paper
• Self-referential instances of the dominating set problem are irreducible

  2026cites this paper
• Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths

  2026cites this paper
• XALP-completeness of parameterized problems on planar graphs

  2026cites this paper
• Graph downsizing: a fast heuristic for querying closely connected subgraphs

  2026cites this paper
• The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching

  2026cites this paper
• Infinite-Domain CSPs and QBF : Fine-Grained and Parameterized Complexity

  2025cites this paper
• Weighted Food Webs Make Computing Phylogenetic Diversity So Much Harder

  2025cites this paper
• On Kernelization with Access to NP-Oracles

  2025influential citation
• Optimal Decision Tree Pruning Revisited: Algorithms and Complexity

  2025cites this paper
• Elimination Distance to Dominated Clusters

  2025cites this paper
• Parameterized complexity of weighted target set selection

  2025cites this paper
• On the Parameterized Complexity of Controlling Amendment and Successive Winners

  2025cites this paper
• Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances

  2025cites this paper
• Aggregating maximal cliques in real-world graphs

  2025cites this paper
• Total domination and open packing in some subclasses of bipartite graphs

  2025cites this paper
• Improving Decision Trees through the Lens of Parameterized Local Search

  2025cites this paper
• Individual Rationality in Topological Distance Games is Surprisingly Hard

  2024cites this paper
• Maximizing Phylogenetic Diversity under Time Pressure: Planning with Extinctions Ahead

  2024cites this paper
• Maximizing Phylogenetic Diversity under Ecological Constraints: A Parameterized Complexity Study

  2024cites this paper
• (Independent) Roman Domination Parameterized by Distance to Cluster

  2024cites this paper
• Separable Convex Mixed-Integer Optimization: Improved Algorithms and Lower Bounds

  2024cites this paper
• Open Packing in Graphs: Bounds and Complexity

  2024cites this paper
• XNLP-hardness of Parameterized Problems on Planar Graphs

  2024cites this paper
• Parameterized Complexity of Dominating Set Variants in Almost Cluster and Split Graphs

  2024cites this paper
• The Computational Complexity of Factored Graphs

  2024cites this paper
• Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis

  2024cites this paper
• The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side

  2024cites this paper
• Unsplittable Flow on a Short Path

  2024cites this paper
• Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths

  2024cites this paper
• Clique Is Hard on Average for Unary Sherali-Adams

  2023cites this paper
• Discovery of Cross Joins

  2023cites this paper
• Efficient size-prescribed k-core search

  2023cites this paper
• How Can We Maximize Phylogenetic Diversity? Parameterized Approaches for Networks

  2023cites this paper
• Counting Vanishing Matrix-Vector Products

  2023cites this paper
• Parameterized Inapproximability Hypothesis under ETH

  2023cites this paper
• A Multivariate Complexity Analysis of the Generalized Noah's Ark Problem

  2023influential citation
• Predicate-Based Explanation of a Reinforcement Learning Agent via Action Importance Evaluation

  2023cites this paper
• Parameterized Counting and Cayley Graph Expanders

  2023cites this paper
• Parameterized Complexity of Factorization Problems

  2023cites this paper
• On Solution Discovery via Reconfiguration

  2023cites this paper
• The Parameterized Complexity of Network Microaggregation

  2023cites this paper
• On Computing Large Temporal (Unilateral) Connected Components

  2023cites this paper
• Maximum Independent Set when Excluding an Induced Minor: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_1 + tK_2$$\

  2023cites this paper
• Reinforcement Learning Explained via Reinforcement Learning: Towards Explainable Policies through Predictive Explanation

  2023cites this paper
• Solution discovery via reconfiguration for problems in P

  2023cites this paper
• Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems

  2023influential citation
• Complexity of Probabilistic Inference in Random Dichotomous Hedonic Games

  2023cites this paper
• Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time

  2023cites this paper
• Improved Hardness of Approximating k-Clique under ETH

  2023cites this paper
• Exact algorithms for restricted subset feedback vertex set in chordal and split graphs

  2023cites this paper
• How to assign volunteers to tasks compatibly ? A graph theoretic and parameterized approach

  2023cites this paper
• Budgeted Matroid Maximization: a Parameterized Viewpoint

  2023cites this paper
• Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes

  2022cites this paper
• Combinatorial and Algorithmic Aspects of Monadic Stability

  2022cites this paper
• Kernelization for Graph Packing Problems via Rainbow Matching

  2022cites this paper
• Finding disjoint paths in networks with star shared risk link groups.

  2022cites this paper
• Stable Matching with Multilayer Approval Preferences: Approvals can be Harder than Strict Preferences

  2022cites this paper
• On the Parameterized Intractability of Determinant Maximization

  2022influential citation
• On the Complexity of Problems on Tree-structured Graphs

  2022cites this paper
• Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees

  2022cites this paper
• Few Induced Disjoint Paths for H-Free Graphs

  2022cites this paper
• Turbocharging Heuristics for Weak Coloring Numbers

  2022cites this paper
• Computing the Tandem Duplication Distance is NP-Hard

  2022cites this paper
• An Algorithmic Framework for Locally Constrained Homomorphisms

  2022cites this paper
• The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side

  2022cites this paper
• Exact and heuristic methods for a workload allocation problem with chain precedence constraints

  2022cites this paper
• Multivariate algorithmics for eliminating envy by donating goods

  2022cites this paper
• Wahlbetrug mit festen und variablen Präferenzen: Eine Komplexitätsanalyse von Kontroll- und Bestechungsproblemen

  2021influential citation
• Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space

  2021cites this paper
• Enumerating Fair Packages for Group Recommendations

  2021cites this paper
• On the complexity of approximately matching a string to a directed graph

  2021cites this paper
• On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs

  2021cites this paper
• Hardness and tractability of the γ-Complete Subgraph problem

  2021cites this paper
• The Complexity of Subelection Isomorphism Problems

  2021cites this paper
• The Multicolored Graph Realization Problem

  2021cites this paper
• The Complexity of Dependency Detection and Discovery in Relational Databases

  2021cites this paper
• Compactors for parameterized counting problems

  2021cites this paper
• Complexity of Locally Fair Allocations on Graphs

  2021cites this paper
• Controlling Entity Integrity with Key Sets

  2021cites this paper
• An Algorithm for the Discovery of Independence from Data

  2021cites this paper
• Parameterized Complexity of Finding Subgraphs with Hereditary Properties on Hereditary Graph Classes

  2021cites this paper
• Almost polynomial factor inapproximability for parameterized k-clique

  2021cites this paper
• Improving the non-compensatory trace-clustering decision process

  2021cites this paper
• Tight FPT Approximation for Constrained k-Center and k-Supplier

  2021cites this paper
• Profile-based optimal stable matchings in the Roommates problem

  2021cites this paper
• On the Δ-interval and the Δ-convexity numbers of graphs and graph products

  2021cites this paper
• Sometimes, Convex Separable Optimization Is Much Harder than Linear Optimization, and Other Surprises

  2021cites this paper
• Constant approximating k-clique is w[1]-hard

  2021cites this paper
• Large Clique is Hard on Average for Resolution

  2021cites this paper
• Beyond Distributed Subgraph Detection: Induced Subgraphs, Multicolored Problems and Graph Parameters

  2021cites this paper
• Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics

  2021cites this paper
• Parameterized Complexity of Conflict-Free Matchings and Paths

  2020cites this paper
• A Retrospective on (Meta) Kernelization

  2020cites this paper
• Catching Numeric Inconsistencies in Graphs

  2020cites this paper
• Discovering Graph Functional Dependencies

  2020cites this paper
• Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure

  2020cites this paper
• Multiplayer games in the context of computational biology

  2020cites this paper
• The Computational Complexity of Evil Hangman

  2020cites this paper
• Increasing the lifetime of sensor networks by a data dissemination model based on a new approximation algorithm

  2020cites this paper