Informatisches Kolloquium SoSe 2002
Informatisches Colloquium Hamburg
|
Wenn nicht anders angegeben, finden die Vorträge montags um 17.15 Uhr im Informatikum, Konrad-Zuse-Hörsaal, Gebäude B, Vogt-Kölln-Str. 30, Hamburg-Stellingen statt. |
8.7.2002 |
Prof. Dr. Ioan Tomescu Extremal and asymptotic properties of irreducible coverings of graphs by cliques
This lecture presents some recurrence formulas for the number of irreducible coverings by edges of the vertices of complete bipartite graphs and the asymptotic behavior of the maximum number of irreducible coverings of an n-vertex graph by cliques and by n-k cliques, respectively, when k is fixed and n tends to infinity. For k=2 and k=3 the structure of these irreducible coverings is described and it is shown that extremal graphs are complete bipartite and these numbers of irreducible coverings are exponential in n. These bounds may serve to the worst case analysis of some algorithms (e.g. Petrick's algorithm) yielding all irreducible coverings (including minimal ones) by prime implicants and by maximal compatibles closed sets of states, respectively, in the case of minimizing disjunctive forms of Boolean functions and the number of states of incompletely specified finite automata of Mealy type. Some open problems and conjectures are proposed. |
Kontakt
|
Prof. Dr. Walther von Hahn Telefon +49 40 42883 2434 |