Dotted interval Graphs
Dotted interval Graphs[edit]
Dotted interval Graphs In graph theory a Dotted interval Graph (DIG) is a generalization of an interval graphs, in which instead of solid intervals we consider dotted intervals, that is, segments of a dotted line.
Definitions[edit]
A dotted interval graph[edit]
is an intersection graph of arithmetic progressions (dotted intervals)
A dotted interval[edit]
is a sequence of integers (dots) on the real line, where the distance between any two consecutive dots is some fixed distance k, called the dotted interval’s jump. We denote by DI(x, y, k, o) (x ≤ y; x, y mod k = o; k ∈ N\{0}; 0 ≤ o < k), the dotted interval such that m ∈ DI(x, y, k, o) if and only if x ≤ m ≤ y and m mod k = o. The parameter o is called the dotted interval’s offset. x or y (or both) can be assigned the value −∞ or ∞ respectively; in either case the DI is an infinite countable set of dots.
DIG[edit]
A graph G = (V, E) is a dotted interval graph (DIG) if it is an intersection graph of a set D of Dotted Intervals
A graph G = (V, E), is a dotted interval graph with maximal jump d, if it is an intersection graph for a set of dotted intervals D, such that for each DI(x, y, k, o) ∈ D, k ≤ d (i.e., all the dotted intervals’ jumps are at most d). The set of all DIGs with maximal jump d is denoted .
Properties of DIG[edit]
Every Graph is a DIG[edit]
Every countable graph is a dotted interval graph. (THEOREM 1.1 p6)
The DIGd Hierarchy[edit]
For all d ≥ 1 , in addition (THEOREM 1.2 p7)
DIGs and Circular Arc Graphs[edit]
DIGs are generalizations of interval graphs. Circular arc graphs are another generalization of interval graphs.
There is a graph that is not a circular arc graph. On the other hand, for every d ≥ 1, there is a circular arc graph that is not a .(THEOREM 3.4 p8)
Hardness of coloring graphs[edit]
For any d, the problem of coloring a is NP hard. The proof is by reduction from coloring of circular-arc graphs.
References[edit]
- Dotted Interval Graphs (article number 9) [1] YONATAN AUMANN, MOSHE LEWENSTEIN, and OREN MELAMUD - Bar-Ilan University, RON PINTER, The Technion , ZOHAR YAKHINI, Agilent Laboratories and TheTechnion
- AUMANN, Y., LEWENSTEIN, M., MELAMUD, O., PINTER, R. Y., AND YAKHINI, Z. 2005. Dotted interval graphs and high throughput genotyping. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 339–348
- AUMANN, Y., MANISTERSKI, E., AND YAKHINI, Z. 2003. Designing optimally multiplexed SNP genotyping assays. In Proceedings of the Workshop on Algorithms in Bioinformatics (WABI), G. Benson and R. D. M. Page, Eds., Lecture Notes in Computer Science, vol. 2812, 255–283.
- BAR-YEHUDA, R., HALLDORSSON ´ , M. M., NAOR, J. S., SHACHNAI, H., AND SHAPIRA, I. 2002. Scheduling split intervals. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms. 732–741
- BRANDSTADT ¨ , A., LE, V. B., AND SPINRAD, J. P. 1999. Graph Classes - A Survey. SIAM, Philadelphia, PA. BUTMAN, A., HERMELIN, D., LEWENSTEIN, M., AND RAWITZ, D. 2007. Optimization problems in multiple-interval graphs. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms. 268–277
- SCHULER, G. D. ET AL. 1996. A gene map of the human genome. Science 274, 540–546. GAREY, M. R., JOHNSON, D. S., MILLER, G. L., AND PAPADIMITRIOU, C. H. 1980. The complexity of coloring circular arcs and chords. SIAM J. Algebraic Discrete Methods 1, 2, 216–227
- GOLUMBIC, M. C. 1994. Algorithmic Graph Theory and Perfect Graphs. Elsevier. GYARF ´ AS´ , A. 1985. On the chromatic number of multiple interval graphs and overlap graphs. Discrete Math. 55, 161–166.
- GYARF ´ AS´ , A. AND WEST, D. 1995. Multitrack interval graphs. Congr. Numer. 109, 109–116. JIANG, M. 2006. Approximating minimum coloring and maximum independent set in dotted interval graphs. Inf. Process. Lett. 98, 1, 29–33.
- KIVIOJA, T., ARVAS, M., KATAJA, K., PENTTILA, M., SOBERLUND, H., AND UKKONEN, E. 2002. Assigning probes into a small number of pools separable by electrophoresis. Bioinformatics 18, 1, 199–206.
- KNAPIK, E. W., GOODMAN, A., EKKER, M., CHEVRETTE, M., DELGADO, J., NEUHAUSS, S., SHIMODA, N., DRIEVER, W., FISHMAN, M. C., AND JACOB, H. J. 1998. A microsatellite genetic linkage map for zebrafish (danio rerio). Nature Genet. 18, 338–343.
- KUMAR, N. AND DEO, N. 1994. Multidimensional interval graphs. Congr. Numer. 102, 45–56. MCKEE, T. A. AND MCMORRIS, F. R. 1999. Topics in Intersection Graph Theory. SIAM, Philadelphia, PA. SHIH, W.-K. AND HSU, W.-L. 1990. An approximation algorithm for coloring circular arc graphs. In Proceedings of SIAM Conference on Discrete Mathematics.
- TROTTER, W. T. AND HARARY, F. 1979. On double and multiple interval graphs. J. Graph Theory 3, 205–211.
- WEST, D. B. AND SHMOYS, D. B. 1984. Recognizing graphs with fixed interval number is NP-complete. Discrete Appl. Math. 8, 295–305.
- YAKHINI, Z., WEBB, P., AND ROTH, R. 2000. Partitioning of polymorphic DNAs. U.S. Patent 6,074,831. YANOVSKY, V. 2008. Approximation algorithm for coloring of dotted interval graphs. Inf. Process. Lett. 108, 1, 41–44.
- ZANE, L., BARGELLONI, L., AND PATARNELLO, T. 2002. Strategies for microsatellite isolation: a review. Molecular Ecology 11, 1–16.
This article "Dotted interval Graphs" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Dotted interval Graphs. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.