On the parameterized complexity of multiple-interval graph problems
type: Item
instance of: scholarly article
title: On the parameterized complexity of multiple-interval graph problems
zbMATH Open document ID: 1161.68038
author: Michael R. Fellows
author: Danny Hermelin
author: Stéphane Vialette
author: Frances Rosamond
published in: Theoretical Computer Science
publication date: 2009-02-19T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5509588
zbMATH Keywords: multiple intervals
zbMATH Keywords: independent set
zbMATH Keywords: dominating set
zbMATH Keywords: clique
zbMATH Keywords: W-hardness
zbMATH Keywords: parameterized complexity
zbMATH Keywords: multicolored clique
Wikidata QID: Q57359825
MaRDI profile type: Publication
full work available at URL: j.tcs.2008.09.065
OpenAlex ID: W2051627428
cites work: Color-coding
cites work: Dotted interval graphs and high throughput genotyping
cites work: Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
cites work: Q4829009
cites work: Algorithms – ESA 2005
cites work: Extracting constrained 2-interval subsets in 2-interval sets
cites work: Q2934605
cites work: On the parameterized complexity of short computation and factorization
cites work: Q4535023
cites work: Q4503944
cites work: Q4027320
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: Q4850549
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Q4198056
cites work: Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
cites work: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
cites work: Q3328583
cites work: Extremal values of the interval number of a graph, II
cites work: Extremal Values of the Interval Number of a Graph
cites work: Q3838186
cites work: Approximation algorithms for hitting objects with straight lines
cites work: Experimental and Efficient Algorithms
cites work: Improved complexity bounds for location problems on the real line
cites work: Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms
cites work: Parameterized Complexity of Independence and Domination on Geometric Graphs
cites work: The interval number of a planar graph: Three intervals suffice
cites work: Recognizing graphs with fixed interval number is NP-complete
DBLP publication ID: journals/tcs/FellowsHRV09
DOI: 10.1016/J.TCS.2008.09.065
description: scientific article; zbMATH DE number 5509588