On the parameterized complexity of some optimization problems related to multiple-interval graphs
From MaRDI portal
Publication:606990
DOI10.1016/J.TCS.2010.09.001zbMath1213.68461OpenAlexW1993342383MaRDI QIDQ606990
Publication date: 19 November 2010
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.09.001
Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (11)
Parameterized Complexity in Multiple-Interval Graphs: Domination ⋮ Recognizing \(d\)-interval graphs and \(d\)-track interval graphs ⋮ On independent set in \(B_1\)-EPG graphs ⋮ Parameterized complexity of conflict-free matchings and paths ⋮ Temporal interval cliques and independent sets ⋮ Interval scheduling and colorful independent sets ⋮ Tractability and approximability of maximal strip recovery ⋮ Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy ⋮ Inapproximability of maximal strip recovery ⋮ Unnamed Item ⋮ Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Recognizing graphs with fixed interval number is NP-complete
- Tree loop graphs
- Approximating the 2-interval pattern problem
- Constant ratio fixed-parameter approximation of the edge multicut problem
- On the parameterized complexity of multiple-interval graph problems
- On recovering syntenic blocks from comparative maps
- Extremal values of the interval number of a graph, II
- On the computational complexity of 2-interval pattern matching problems
- Algorithmic graph theory and perfect graphs
- Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
- On double and multiple interval graphs
- The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants
- On Restrictions of Balanced 2-Interval Graphs
- On the Parameterized Complexity of Some Optimization Problems Related to Multiple-Interval Graphs
- Inapproximability of Maximal Strip Recovery: II
- Recognizing d-Interval Graphs and d-Track Interval Graphs
- Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
- On the Tractability of Maximal Strip Recovery
- Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms
- Planar Capacitated Dominating Set Is W[1-Hard]
- What Makes Equitable Connected Partition Easy
- Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms
- Extremal Values of the Interval Number of a Graph
- Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
- Scheduling Split Intervals
- Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
This page was built for publication: On the parameterized complexity of some optimization problems related to multiple-interval graphs
