On the parameterized complexity of some optimization problems related to multiple-interval graphs
type: Item
instance of: scholarly article
title: On the parameterized complexity of some optimization problems related to multiple-interval graphs
zbMATH Open document ID: 1213.68461
published in: Theoretical Computer Science
publication date: 2010-11-19T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68M20
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5817531
zbMATH Keywords: computational complexity
zbMATH Keywords: geometric intersection graph
zbMATH Keywords: bioinformatics
author: Minghui Jiang
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.09.001
OpenAlex ID: W1993342383
cites work: Tree loop graphs
cites work: Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
cites work: Scheduling Split Intervals
cites work: Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
cites work: Planar Capacitated Dominating Set Is W[1]-Hard
cites work: Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms
cites work: Q2934605
cites work: On recovering syntenic blocks from comparative maps
cites work: Approximating the 2-interval pattern problem
cites work: The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants
cites work: Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
cites work: Q4393480
cites work: What Makes Equitable Connected Partition Easy
cites work: On the parameterized complexity of multiple-interval graph problems
cites work: On Restrictions of Balanced 2-Interval Graphs
cites work: Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms
cites work: Algorithmic graph theory and perfect graphs
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: Inapproximability of Maximal Strip Recovery: II
cites work: On the Parameterized Complexity of Some Optimization Problems Related to Multiple-Interval Graphs
cites work: Recognizing d-Interval Graphs and d-Track Interval Graphs
cites work: Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
cites work: Constant ratio fixed-parameter approximation of the edge multicut problem
cites work: On double and multiple interval graphs
cites work: On the computational complexity of 2-interval pattern matching problems
cites work: On the Tractability of Maximal Strip Recovery
cites work: Recognizing graphs with fixed interval number is NP-complete
DOI: 10.1016/J.TCS.2010.09.001
description: scientific article; zbMATH DE number 5817531