Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
From MaRDI portal
Publication:2375953
DOI10.1007/s00453-012-9651-5zbMath1267.68121OpenAlexW2766871017MaRDI 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
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (7)
Trees, paths, stars, caterpillars and spiders ⋮ Trees, Paths, Stars, Caterpillars and Spiders ⋮ Interval scheduling and colorful independent sets ⋮ The interval number of a planar graph is at most three ⋮ On interval representations of graphs ⋮ Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review ⋮ Precedence thinness in graphs
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)
This page was built for publication: Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
