Graph-Theoretic Concepts in Computer Science: 20th International Workshop. WG '94, Herrsching, Germany, June 16 - 18, 1994. Proceedings

by Ernst W. Mayr (Editor)

Domino treewidth.- A lower bound for treewidth and its consequences.- Tree-width and path-width of comparability graphs of interval orders.- A declarative approach to graph based modeling.- Multilevel graph grammars.- The algorithmic use of hypertree structure and maximum neighbourhood orderings.- On domination elimination orderings and domination graphs.- Complexity of graph covering problems.- Dominoes.- GLB-closures in directed acyclic graphs and their applications.- Minimum vertex cover, distributed decision-making, and communication complexity.- Cartesian products of graphs as spanning subgraphs of de Bruijn graphs.- Specification of graph translators with triple graph grammars.- Using programmed graph rewriting for the formal specification of a configuration management system.- Exponential time analysis of confluent and boundary eNCE graph languages.- Time-optimal tree computations on sparse meshes.- Prefix graphs and their applications.- The complexity of broadcasting in planar and decomposable graphs.- The maximal f-dependent set problem for planar graphs is in NC.- On-line convex planarity testing.- Book embeddings and crossing numbers.- Measuring the distance to series-parallelity by path expressions.- Labelled trees and pairs of input-output permutations in priority queues.- Rankings of graphs.- Bypass strong V-structures and find an isomorphic labelled subgraph in linear time.- Efficient algorithms for a mixed k-partition problem of graphs without specifying bases.- Fugitive-search games on graphs and related parameters.- New approximation results on graph matching and related problems.- New lower bounds and hierarchy results for restricted branching programs.- On-line algorithms for satisfiability problems with uncertainty.- NC algorithms for antidirected hamiltonian paths and cycles in tournaments.- Directed path graph isomorphism.

436 pages, Paperback

Published March 12, 2014

About the author

For the computer scientist, see Ernst Wilhelm Meyr

Ernst Walter Mayr (July 5, 1904 – February 3, 2005) was one of the 20th century's leading evolutionary biologists. He was also a renowned taxonomist, tropical explorer, ornithologist, and historian of science. His work contributed to the conceptual revolution that led to the modern evolutionary synthesis of Mendelian genetics, systematics, and Darwinian evolution, and to the development of the biological species concept.

Although Charles Darwin and others posited that multiple species could evolve from a single common ancestor, the mechanism by which this occurred was not understood, creating the species problem. Ernst Mayr approached the problem with a new definition for the concept of species. In his book Systematics and the Origin of Species (1942) he wrote that a species is not just a group of morphologically similar individuals, but a group that can breed only among themselves, excluding all others. When populations within a species become isolated by geography, feeding strategy, mate selection, or other means, they may start to differ from other populations through genetic drift and natural selection, and over time may evolve into new species. The most significant and rapid genetic reorganization occurs in extremely small populations that have been isolated (as on islands).

His theory of peripatric speciation (a more precise form of allopatric speciation which he advanced), based on his work on birds, is still considered a leading mode of speciation, and was the theoretical underpinning for the theory of punctuated equilibrium, proposed by Niles Eldredge and Stephen Jay Gould. Mayr is sometimes credited with inventing modern philosophy of biology, particularly the part related to evolutionary biology, which he distinguished from physics due to its introduction of (natural) history into science.