Browsing by Author "Vollmerhaus, Walter"
Now showing 1 - 9 of 9
Results Per Page
Sort Options
- ItemOpen AccessA Semi-automated process for runway location in mountainous terrain(1987) Singh, K. Romi; Vollmerhaus, Walter
- ItemMetadata onlyFUNDAMENTAL THEORECTICAL CONCEPTS, SELECTED FOR THE STARTING COMPUTER SCIENTIST(1985-12-01) Vollmerhaus, WalterThis is a report on the subjects that I have chosen as material for an introductory course to the theory of computer science. I have been teaching such a course for many years and I have tried out many different approaches - the latest one, described here, seems to be the most successful one so far. My main objective has been to introduce the fundamental concepts of Computability and Specification, Implementation and Verification to the student in such a way that the essential heuristic ideas, on which these concepts are based become transparent. It is a nontrivial task to find a good compromise between the amount of formal detail that is needed to describe these concepts properly and between the amount of informal and intuitive argument that is necessary for the student to clearly see the underlying ideas.
- ItemOpen AccessA KURATOWSKI THEOREM FOR ORIENTABLE SURFACES(1987-12-01) Vollmerhaus, WalterLet $SIGMA$ denote a 2-dimensional surface. A graph $G$ is irreducible for $SIGMA$ provided that $G$ does not embed into $SIGMA$, but every proper subgraph of $G$ does. Let $I$($SIGMA$) denote the set of graphs with vertex degree at least three that are irreducible for $SIGMA$. In this paper we prove that $I$($SIGMA$) is finite for each orientable surface. Together with the result by D. Archdeacon and Huneke, stating that $I$($SIGMA$) is finite for each non-orientable surface, this settles a conjecture of Erd$o dotdot$'s from the 1930s that $I$($SIGMA$) is finite for each surface $SIGMA$. Let $SIGMA sub n$ denote the closed orientable surface of genus $n$. We also write $gamma$($SIGMA$) to denote the genus of orientable surface $SIGMA$. Let $G$ be a finite graph. An embedding of $G$ into a surface $SIGMA$ is a topological map \o'0 /'$:G -> SIGMA$. The orientable genus $gamma$($G$) of the graph $G$ is defined to be the least value of $gamma$($SIGMA$) for all orientable surfaces $SIGMA$ into which $G$ can be embedded. Let $P$ be a property of a graph $G$. We say that $G$ is $P$-critical provided that $G$ has property $P$ but no proper subgraph of $G$ has property $P$. For example, if $P$ is the property that $gamma$($G$) $>= 1$, then the $P$-critical graphs are the two Kuratowski graphs $K sub 5$ and $K sub 3,3$. In general, if $P$ is the property that $gamma$($G$) $>= n$, then a $P$-critical graph can be embedded in $SIGMA sub n$ but not in $SIGMA sub {n - 1}$. Such a $P$-critical graph is also called irreducible for the surface $SIGMA sub {n - 1}$. For any surface $SIGMA$, let $I$($SIGMA$) denote the set of graphs that have no vertices of degree two and are irreducible for $SIGMA$.
- ItemMetadata onlyON COMPUTING A SPECIAL CLASS OF IRREDUCIBLE NON-EMBEDDED GRAPHS FOR THE PROJECTIVE PLANE II(1982-12-01) Vollmerhaus, WalterThis paper is a continuation of [2], presenting some more results leading to establishing a complete list of irreducible non-embeddable graphs for the projective plane. The main result presented here is the following theorem: all irreducible non-embeddable graphs for the projective plane which have a subgraph contractable to $E sub 2$ and do not have a subgraph contractable to $E sub 1$ or $GAMMA sub 1$ or $K sub 3,4$ are contractable to one of the 3 graphs $F sub 3, F sub 4$ or $E sub 20$ in [E].
- ItemMetadata onlyON COMPUTING A SPECIAL CLASS OF IRREDUCIBLE NON-EMBEDDABLE GRAPHSFOR THE PROJECTIVE PLANE(1981-12-01) Vollmerhaus, WalterThis paper is a continuation of [1], presenting some more results leading to establishing a complete list of irreducible non-embeddable graphs for the projective plane. The main result presented here is the following theorem: All irreducible non-embeddable graphs for the projective plane which have a subgraph contractable to $E sub 1$ and do not have a subgraph contractable to $GAMMA sub 1$ or $K sub 3,4$, are contractable to the graph $F sub 10$ in [2].
- ItemMetadata onlyON COMPUTING ALL IRREDUCIBLE NON-EMBEDDABLE GRAPHS FOR THE PROJECTIVE PLANE THAT CONTAIN K sub 3,4(1983-12-01) Vollmerhaus, WalterIn this paper we compute a complete list of all 3-connected irreducible graphs containing a subgraph contractable to K sub 3,4 that are not embeddable into the projective plane.
- ItemOpen AccessON COMPUTING ALL MINIMAL GRAPHS THAT ARE NOT EMBEDDABLE INTO THE PROJECTIVE PLANEPART 1(1986-12-01) Vollmerhaus, WalterNo Abstract
- ItemEmbargoOn Single-file diffusion models(1972) Wan, Maxime; Vollmerhaus, Walter
- ItemMetadata onlyPROVING THE COMPLETENESS OF A LIST OF 19 IRREDUCIBLE NON-EMBEDDABLE GRAPHSFOR THE PROJECTIVE PLANE THAT CONTAIN 3,4(1984-12-01) Vollmerhaus, WalterIn this paper we show that the list A sub 2 , B sub 1 , B sub 7 , C sub 3 , C sub 4 , C sub 7 , D sub 2 , D sub 3 , D sub 9 , D sub 12 , D sub 17 , E sub 2 , E sub 3 , E sub 5, E sub 11 , E sub 18 , E sub 19 , E sub 27 , G is the complete list of all 3-connected irreducible graphs that cannot be embedded into the projective plane and that contain {K sub 3,4} as a minor. The graphs are named as in [1].