×

Algorithmic characterizations of interval orderd hypergraphs and applications. (English) Zbl 0810.68105

Summary: We present two algorithmic characterizations of interval (ordered) hypergraphs. The first one provides a criterion for a given partial ordering of the vertex set of some interval hypergraph to admit a linear extension which preserves the interval structure. The second one tells us when a given partial embedding of some ordered hypergraph into the real line can be extended into an interval representation of this hypergraph. We use these theoretical results in order to design some greedy heuristic for a scheduling theory version of the problem of finding an optimal arrangement for consecutive retrieval.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C65 Hypergraphs
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B35 Deterministic scheduling theory in operations research
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baker, K. R., Introduction to Sequencing and Scheduling (1974), Wiley: Wiley New York
[2] Baptiste, P.; Favrel, J., Résolution de problèmes d’ordonnancements par graphes d’intervalles et treillis de galois, RAIRO (Automatic systems analysis and control), 18, 4 (1984) · Zbl 0549.90054
[3] Benzer, S., On the topology of the genetic fine structure, Proc. Acad. Sci. USA, 45, 1607-1620 (1959)
[4] Berge, C., Graphes et Hypergraphes (1974), Dunod: Dunod Paris, Chapitres 5 et 6 · Zbl 0213.25702
[5] Booth, K. S.; Lueker, G. S., Testing for the consecutive one’s property, J. Comput. Sci., 13, 35-58 (1976)
[6] Carter, M., A survey on practical applications of examination timetabling algorithms, Oper. Res., 34, 2, 193-202 (1986)
[7] Chein, M.; Habib, M., The jump number of dags and posets: an introduction, Ann. Discrete Math., 9, 189-194 (1980) · Zbl 0445.05048
[8] Duchet, P., Problèmes de représentations et noyaux, Thèse d’état Paris, VI (1981)
[9] Dushnik, B.; Miller, W., Partially ordered sets, Amer. J. Math., 63, 600-610 (1941) · JFM 67.0157.01
[10] Fulkerson, D. R.; Gross, D. A., Incidence matrices and interval graphs, Pacific J. Math., 15, 835-855 (1965) · Zbl 0132.21001
[11] Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), Freeman: Freeman New York · Zbl 0411.68039
[12] Ghosh, S. P., File organization: the consecutive retrieval property, Comm. ACM, 9, 802-808 (1975) · Zbl 0246.68004
[13] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[14] Grahamson, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy-kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., 5, 287-326 (1979) · Zbl 0411.90044
[15] Heller, I.; Hoffman, A. J., On unimodular matrices, Pacific J. Math., 12, 1321-1327 (1962) · Zbl 0115.01104
[16] Kindall, D. G., Incidence matrices, interval graphs and seriation in Archeology, Pacific J. Math., 28, 3, 565-570 (1969) · Zbl 0185.03301
[17] L.T. Kou, Polynomial complete consecutive information retrieval problems, SIAM J. Comput. 6, pp. 67-75.; L.T. Kou, Polynomial complete consecutive information retrieval problems, SIAM J. Comput. 6, pp. 67-75. · Zbl 0354.68036
[18] Luccio, F.; Preparata, F. P., Storage for consecutive retrieval, Inform. Process Lett., 5, 3, 68-71 (1976) · Zbl 0354.68034
[19] Mohring, R. H.; Radermacher, F. J., Scheduling problems with resource duration interactions, Methods of Oper. Res., 48, 423-452 (1984) · Zbl 0561.90048
[20] Schrijver, A., Theory of Linear and Integer Programming (1986), Wiley Interscience: Wiley Interscience New York, Chapters 19 and 20 · Zbl 0665.90063
[21] Tucker, A. C., Structure theorem for the consecutive 1’s property, J. Combin. Theory Ser. B, 12, 153-162 (1972) · Zbl 0208.52402
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.