Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
From MaRDI portal
Publication:2375953
DOI10.1007/s00453-012-9651-5zbMath1267.68121MaRDI QIDQ2375953
Publication date: 25 June 2013
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9651-5
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
On interval representations of graphs, Interval scheduling and colorful independent sets, Trees, paths, stars, caterpillars and spiders, Precedence thinness in graphs, The interval number of a planar graph is at most three, Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review, Trees, Paths, Stars, Caterpillars and Spiders
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Inapproximability of maximal strip recovery
- On the parameterized complexity of some optimization problems related to multiple-interval graphs
- Simple linear time recognition of unit interval graphs
- Recognizing graphs with fixed interval number is NP-complete
- Tree loop graphs
- Approximating the 2-interval pattern problem
- On recovering syntenic blocks from comparative maps
- Determining the interval number of a triangle-free graph
- A short proof of the degree bound for interval number
- The linear arboricity of graphs
- On the unit interval number of a graph
- Extremal values of the interval number of a graph, II
- Colorings and orientations of graphs
- On the computational complexity of 2-interval pattern matching problems
- Beyond the flow decomposition barrier
- On double and multiple interval graphs
- On Restrictions of Balanced 2-Interval Graphs
- Strip Graphs: Recognition and Scheduling
- Recognizing d-Interval Graphs and d-Track Interval Graphs
- Complexité de l'arboricité linéaire d'un graphe
- Extremal Values of the Interval Number of a Graph
- A sharp edge bound on 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)
