zbMATH — the first resource for mathematics

Directed hypergraphs and applications. (English) Zbl 0771.05074
Summary: We deal with directed hypergraphs as a tool to model and solve some classes of problems arising in operations research and in computer science. Concepts such as connectivity, paths and cuts are defined. An extension of the main duality results to a special class of hypergraphs is presented. Algorithms to perform visits of hypergraphs and to find optimal paths are studied in detail. Some applications arising in propositional logic, And-Or graphs, relational databases and transportation analysis are presented.

05C65 Hypergraphs
05C90 Applications of graph theory
68R10 Graph theory (including graph drawing) in computer science
05C38 Paths and cycles
05C85 Graph algorithms (graph-theoretic aspects)
05C40 Connectivity
68P15 Database theory
Full Text: DOI
[1] Ausiello, G.; D’Atri, A.; Saccà, D., Graph algorithms for functional dependency manipulation, J. ACM, 30, 752-766, (1983) · Zbl 0624.68089
[2] Ausiello, G.; D’Atri, A.; Saccà, D., Strongly equivalent directed hypergraphs, (), 1-25 · Zbl 0562.05036
[3] Ausiello, G.; D’Atri, A.; Saccà, D., Minimal representation of directed hypergraphs, SIAM J. comput., 15, 418-431, (1986) · Zbl 0602.68056
[4] Ausiello, G.; Italiano, G.F.; Nanni, U., Dynamic maintenance of directed hypergraphs, Theoret. comput. sci., 72, 97-117, (1990) · Zbl 0699.68027
[5] Berge, C., Graphs and hypergraphs, (1973), North-Holland Amsterdam · Zbl 0483.05029
[6] Berge, C., Minimax theorems for normal hypergraphs and balanced hypergraphs — a survey, (), 3-19 · Zbl 0554.05052
[7] Berge, C., Huypergraphs: combinatorics of finite sets, (1989), North-Holland Amsterdam
[8] Boley, H., Directed recursive labelnode hypergraphs: a new representation language, Artificial intelligence, 9, 49-85, (1977) · Zbl 0357.68100
[9] Cook, S., The complexity of theorem-proving procedures, Proceedings 3th ACM symposium on theory of computing, 151-158, (1971)
[10] Dowling, W.; Gallier, J., Linear-time algorithms for testing the satisfiability of propositional Horn formulae, J. logic programming, 3, 267-284, (1984) · Zbl 0593.68062
[11] Furtado, A.L., Formal aspects of the relational model, Inform. systems, 3, 131-140, (1978)
[12] Gallo, G.; Longo, G.; Nguyen, S.; Pallottino, S., Gli ipergrafi orientati: un nuovo approccio per la formulazione e risoluzione di problemi combinatori, Atti AIRO, 89, 217-236, (1989)
[13] Gallo, G.; Pallottino, S., Shortest path methods: a unifying approach, Math. programming stud., 26, 38-64, (1986) · Zbl 0605.90123
[14] Gallo, G.; Urbani, G., Algorithms for testing the satisfiability of propositional formulae, J. logic programming, 7, 45-61, (1989) · Zbl 0672.68044
[15] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[16] Gnesi, S.; Montanari, U.; Martelli, A., Dynamic programming as graph searching: an algebraic approach, J. ACM, 28, 737-751, (1981) · Zbl 0471.90092
[17] Itai, A.; Makowsky, J., On the complexity of Herbrand’s theorem, () · Zbl 0641.68143
[18] Italiano, G.F.; Nanni, U., On line maintenance of minimal directed hypergraphs, (), 335-349
[19] Jaumard, B.; Simeone, B., On the complexity of the maximum satisfiability problem for Horn formulas, Inform. process. lett., 26, 1-4, (1987) · Zbl 0638.03036
[20] Jeroslow, R.G.; Martin, R.K.; Rardin, R.R.; Wang, J., Gainfree leontiev flows problems, ()
[21] Knuth, D.E., The art of computer programming, (1968), Addison-Wesley Reading, MA · Zbl 0191.17903
[22] Levi, G.; Sirovich, F., Generalized and/or graphs, Artificial intelligence, 7, 243-259, (1976) · Zbl 0333.68063
[23] Longo, G., Per una nuova teoria degli ipergrafi orientati, Tesi di laurea, (1989), Dipartimento di Informatica, Università di Pisa Pisa
[24] Maier, D., Minimum covers in the relational data base model, J. ACM, 27, 664-674, (1980) · Zbl 0466.68085
[25] Martelli, A.; Montanari, U., Additive AND/OR graphs, Proc. IJCAI, 3, 1-11, (1973)
[26] Martin, J., Computer data base organization, (1977), Prentice-Hall Englewood Cliffs, NJ
[27] Nguyen, S.; Pallottino, S., Assegnamento dei passeggeri ad un sistema di linee urbane: determinazione degli ipercammini minimi, Ricerca operativa, 38, 28-47, (1986)
[28] Nguyen, S.; Pallottino, S., Equilibrium traffic assignment for large scale transit networks, European J. oper. res., 37, 176-186, (1988) · Zbl 0649.90049
[29] Nguyen, S.; Pallottino, S., Hyperpaths and shortest hyperpaths, (), 258-271 · Zbl 0678.90088
[30] Nilsson, N.J., Problem solving methods in artificial intelligence, (1971), McGraw-Hill New York
[31] Nilsson, N.J., Principles of artificial intelligence, (1980), Morgan Kaufmann Los Altos, CA · Zbl 0422.68039
[32] Smith, H.C., Database design: composing fully normalized tables from a rigourous dependency diagram, Comm. ACM, 28, 826-838, (1985)
[33] Torres, A.F.; Aráoz, J.D., Combinatorial models for searching in knowledge bases, Acta cient. venezolana, 39, 387-394, (1988) · Zbl 0668.68115
[34] Ullman, J.D., Principles of database systems, (1982), Computer Science Press Rockville, MD · Zbl 0558.68078
[35] Yang, C.C., Relational databases, (1986), Prentice-Hall Englewood Cliffs, NJ
[36] Yang, C.C., Deduction graphs: an algorithm and applications, IEEE trans. software engrg., 15, 60-67, (1989) · Zbl 0667.68113
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.