Recognizing \(d\)-interval graphs and \(d\)-track interval graphs

DOI10.1007/s00453-012-9651-5zbMath1267.68121OpenAlexW2766871017MaRDI QIDQ2375953

Ming-Hui Jiang

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

zbMATH Keywords

computational complexitybioinformaticsgraph recognition

Mathematics Subject Classification ID

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