✦ LIBER ✦

Generalized and/or graphs

✍ Scribed by Giorgio Levi; Franco Sirovich

Publisher: Elsevier Science
Year: 1976
Tongue: English
Weight: 974 KB
Volume: 7
Category: Article
ISSN: 0004-3702
DOI: 10.1016/0004-3702(76)90006-0

No coin nor oath required. For personal study only.

✦ Synopsis

A generalization of AND/OR graphs is introduced as a problem solving model, in which subproblem interdependence in problem reduction can be explicitly accounted for. An ordered-search algorithm is given to fred a solution. The algorithm is proven to be admissible and optimal Examples are given which show the application of the formalism to problems which cannot be modelled by AND [OR graphs. Generalized AND[OR graphs are finally shown to he equivalent to type 0 grammars. Finding a solution of a generalized AND[OR graph is shown to be equivalent to deriving a sentence in the corresponding type 0 grammar.

📜 SIMILAR VOLUMES

Generalized line graphs

✍ Dragoš Cvetkovic̀; Michael Doob; Slobodan Simic̀ 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 775 KB

## Abstract Generalized line graphs extend the ideas of both line graphs and cocktail party graphs. They were originally motivated by spectral considerations. in this paper several (nonspectral) classical theorems about line graphs are extended to generalized line graphs, including the derivation a

Generalized steinhaus graphs

✍ Neal Brand; Margaret Morton 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 584 KB

## Abstract A generalized Steinhaus graph of order __n__ and type __s__ is a graph with __n__ vertices whose adjacency matrix (__a__~i,j~) satisfies the relation magnified image where 2 ≦__i__≦__n__−1, __i__ + __s__(__i__ − 1 ≦ __j__ ≦ __n__, __c__~r,i,j~ ϵ {0,1} for all 0 ≦ __r__ ≦ __s__(__i__) −1

Generalized Cayley graphs

✍ Dragan Marušič; Raffaele Scapellato; Norma Zagaglia Salvi 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 403 KB

## We introduce the concept of generalized Cayley graphs and study their properties, in particular relative to double coverings of graphs.

Generalized Pigeonhole Properties of Gra

Generalized Pigeonhole Properties of Graphs and Oriented Graphs

✍ Anthony Bonato; Peter J Cameron; Dejan Delić; Stéphan Thomassé 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 152 KB

A relational structure A satisfies the P(n, k) property if whenever the vertex set of A is partitioned into n nonempty parts, the substructure induced by the union of some k of the parts is isomorphic to A. The P(2, 1) property is just the pigeonhole property, (P), introduced by Cameron, and studied

Generalized Split Graphs and Ramsey Numb

Generalized Split Graphs and Ramsey Numbers

✍ András Gyárfás 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 283 KB

A graph G is called a ( p, q)-split graph if its vertex set can be partitioned into A, B so that the order of the largest independent set in A is at most p and the order of the largest complete subgraph in B is at most q. Applying a well-known theorem of Erdo s and Rado for 2-systems, it is shown th

Infinite generalized friendship graphs

✍ Charles Delorme; Geňa Hahn 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 312 KB

We give necessary and sufficient conditions for the existence of infinite generalized friendship graphs and show that there are 2 c non-isomorphic ones of each admissible order c and chromatic number. Further we prove that such graphs and their complements are almost always regular of degree equal t