Parameterized complexity of finding subgraphs with hereditary properties.
type: Item
instance of: scholarly article
title: Parameterized complexity of finding subgraphs with hereditary properties.
zbMATH Open document ID: 1061.68061
DOI: 10.1016/S0304-3975(01)00414-5
author: Venkatesh Raman
author: Subhash Khot
published in: Theoretical Computer Science
publication date: 2003-01-21T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1857105
zbMATH Keywords: Parameterized complexity
zbMATH Keywords: Hereditary properties
zbMATH Keywords: Ramsey numbers
MaRDI profile type: Publication
cites work: Fixed-parameter tractability of graph modification problems for hereditary properties
cites work: Perfect Code is \(W[1]\)-complete
cites work: Fixed-Parameter Tractability and Completeness I: Basic Results
cites work: Fixed-parameter tractability and completeness II: On completeness for W[1]
cites work: Q4503944
cites work: The complexity of irredundant sets parameterized by size
cites work: On the parametric complexity of schedules to minimize tardy tasks.
cites work: Q4198056
cites work: Q3328583
cites work: Q5572939
cites work: The node-deletion problem for hereditary properties is NP-complete
cites work: Parameterizing above Guaranteed Values: MaxSat and MaxCut
cites work: Q4944968
cites work: Edge-Deletion Problems
full work available at URL: s0304-3975(01)00414-5
OpenAlex ID: W1488421129
Recommended article: Q2766822
Recommended article: Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
Recommended article: Q4272117
Recommended article: Q5492624
Recommended article: The Parameterized Complexity of Finding Point Sets with Hereditary Properties
Recommended article: Fixed-parameter tractability of graph modification problems for hereditary properties
Recommended article: Hereditary classes of graphs: a parametric approach
Recommended article: Parameterized complexity of finding connected induced subgraphs
Recommended article: Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes
Recommended article: Parameterized complexity of finding regular induced subgraphs
description: scientific article; zbMATH DE number 1857105