This volume presents the proceedings of the 10th International Workshop on Combinatorial Image Analysis, held December 1 3, 2004, in Auckland, New Zealand. Prior meetings took place in Paris (France, 1991), Ube (Japan, 1992), Washington DC (USA, 1994), Lyon (France, 1995), Hiroshima (Japan, 1997), Madras (India, 1999), Caen (France, 2000), Philadelphia (USA, 2001), and - lermo (Italy, 2003). For this workshop we received 86 submitted papers from 23 countries. Each paper was evaluated by at least two independent referees. We selected 55 papers for the conference. Three invited lectures by Vladimir Kovalevsky (Berlin), Akira Nakamura (Hiroshima), and Maurice Nivat (Paris) completed the program. Conference papers are presented in this volume under the following topical part titles: discrete tomography (3 papers), combinatorics and computational models (6), combinatorial algorithms (6), combinatorial mathematics (4), d- ital topology (7), digital geometry (7), approximation of digital sets by curves and surfaces (5), algebraic approaches (5), fuzzy image analysis (2), image s- mentation (6), and matching and recognition (7). These subjects are dealt with in the context of digital image analysis or computer vision."

Bipartite graphs are perhaps the most basic of objects in graph theory, both from a theoretical and practical point of view. Until now, they have been considered only as a special class in some wider context. This work deals solely with bipartite graphs, providing traditional material as well as many new and unusual results. The authors illustrate the theory with many applications, especially to problems in timetabling, chemistry, communication networks and computer science. The material is accessible to any reader with a graduate understanding of mathematics and will be of interest to specialists in combinatorics and graph theory.

This volume consists of the refereed papers presented at the Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory (IJCCGGT 2003), held on September 13 16, 2003 at ITB, Bandung, Indonesia. This conf- ence can also be considered as a series of the Japan Conference on Discrete and Computational Geometry (JCDCG), which has been held annually since 1997. The ?rst ?ve conferences of the series were held in Tokyo, Japan, the sixth in Manila, the Philippines, in 2001, and the seventh in Tokyo, Japan in 2002. The proceedings of JCDCG 1998, JCDCG 2000 and JCDCG 2002 were p- lished by Springer as part of the series Lecture Notes in Computer Science: LNCS volumes 1763, 2098 and 2866, respectively. The proceedings of JCDCG 2001 were also published by Springer as a special issue of the journal Graphs and Combinatorics, Vol. 18, No. 4, 2002. TheorganizersaregratefultotheDepartmentofMathematics, InstitutTek- logi Bandung (ITB) and Tokai University for sponsoring the conference. We also thank all program committee members and referees for their excellent work. Our big thanks to the principal speakers: Hajo Broersma, Mikio Kano, Janos Pach andJorgeUrrutia.Finally, ourthanksalsogoestoallourcolleagueswhoworked hard to make the conference enjoyable and successful. August 2004 Jin Akiyama Edy Tri Baskoro Mikio Kano Organization The Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory (IJCCGGT) 2003 was organized by the Department of Mathematics, InstitutTeknologiBandung(ITB)IndonesiaandRIED, TokaiUniversity, Japan

This self-contained book examines results on transfinite graphs and networks achieved through a continuing research effort during the past several years. These new results, covering the mathematical theory of electrical circuits, are different from those presented in two previously published books by the author, Transfiniteness for Graphs, Electrical Networks, and Random Walks and Pristine Transfinite Graphs and Permissive Electrical Networks.

Two initial chapters present the preliminary theory summarizing all essential ideas needed for the book and will relieve the reader from any need to consult those prior books. Subsequent chapters are devoted entirely to novel results and cover:

* Connectedness ideas---considerably more complicated for transfinite graphs as compared to those of finite or conventionally infinite graphs----and their relationship to hypergraphs

* Distance ideas---which play an important role in the theory of finite graphs---and their extension to transfinite graphs with more complications, such as the replacement of natural-number distances by ordinal-number distances

* Nontransitivity of path-based connectedness alleviated by replacing paths with walks, leading to a more powerful theory for transfinite graphs and networks

Additional features include:

* The use of nonstandard analysis in novel ways that leads to several entirely new results concerning hyperreal operating points for transfinite networks and hyperreal transients on transfinite transmission lines; this use of hyperreals encompasses for the first time transfinite networks and transmission lines containing inductances and capacitances, in addition to resistances

* A useful appendix with concepts from nonstandard analysis used in the book

* May serve as a reference text or as a graduate-level textbook in courses or seminars

Graphs and Networks: Transfinite and Nonstandard will appeal to a diverse readership, including graduate students, electrical engineers, mathematicians, and physicists working on infinite electrical networks. Moreover, the growing and presently substantial number of mathematicians working in nonstandard analysis may well be attracted by the novel application of the analysis employed in the work.

ISBN 0-8176-4292-7

Boundaries and Hulls of Euclidean Graphs: From Theory to Practice presents concepts and algorithms for finding convex, concave and polygon hulls of Euclidean graphs. It also includes some implementations, determining and comparing their complexities. Since the implementation is application-dependent, either centralized or distributed, some basic concepts of the centralized and distributed versions are reviewed. Theoreticians will find a presentation of different algorithms together with an evaluation of their complexity and their utilities, as well as their field of application. Practitioners will find some practical and real-world situations in which the presented algorithms can be used.

The combinatorial theory of species, introduced by Joyal in 1980, provides a unified understanding of the use of generating functions for both labeled and unlabeled structures as well as a tool for the specification and analysis of these structures. This key reference presents the basic elements of the theory and gives a unified account of its developments and applications. The authors offer a modern introduction to the use of various generating functions, with applications to graphical enumeration, Polya Theory and analysis of data structures in computer science, and to other areas such as special functions, functional equations, asymptotic analysis, and differential equations.

This volume presents up-to-date research on finite geometries and designs, a key area in modern applicable mathematics. An introductory chapter discusses topics presented in each of the main chapters, and is followed by articles from leading international figures in this field. These include a discussion of the current state of finite geometry from a group-theoretical viewpoint, and surveys of difference sets and of small embeddings of partial cycle systems into Steiner triple systems. Also presented are successful searches for spreads and packing of designs, rank three geometries with simplicial residues and generalized quadrangles satisfying Veblen's Axiom. In addition, there are articles on new 7-designs, biplanes, various aspects of triple systems, and many other topics. This book will be a useful reference for researchers working in finite geometries, design theory or combinatorics in general.

This volume consists of the papers presented by the invited lecturers at the 16th British Combinatorial Conference. This biennial meeting is one of the most important for combinatorialists, attracting leading figures in the field. This overview of up-to-date research will be a valuable resource for researchers and graduate students.

The first of two companion volumes on anabelian algebraic geometry, this book contains the famous, but hitherto unpublished manuscript 'Esquisse d'un Programme' (Sketch of a Program) by Alexander Grothendieck. This work, written in 1984, fourteen years after his retirement from public life in mathematics, together with the closely connected letter to Gerd Faltings, dating from 1983 and also published for the first time in this volume, describe a powerful program of future mathematics, unifying aspects of geometry and arithmetic via the central point of moduli spaces of curves; it is written in an artistic and informal style. The book also contains several articles on subjects directly related to the ideas explored in the manuscripts; these are surveys of mathematics due to Grothendieck, explanations of points raised in the Esquisse, and surveys on progress in the domains described there.

Paul Erdoes was one of the greatest mathematicians of this century, known the world over for his brilliant ideas and stimulating questions. On the date of his 80th birthday a conference was held in his honour at Trinity College, Cambridge. Many leading combinatorialists attended. Their subsequent contributions are collected here. The areas represented range from set theory and geometry, through graph theory, group theory and combinatorial probability, to randomised algorithms and statistical physics. Erdoes himself was able to give a survey of recent progress made on his favourite problems. Consequently this volume, consisting of in-depth studies at the frontier of research, provides a valuable panorama across the breadth of combinatorics as it is today.

This 1997 work explores the role of probabilistic methods for solving combinatorial problems. These methods not only provide the means of efficiently using such notions as characteristic and generating functions, the moment method and so on but also let us use the powerful technique of limit theorems. The basic objects under investigation are nonnegative matrices, partitions and mappings of finite sets, with special emphasis on permutations and graphs, and equivalence classes specified on sequences of finite length consisting of elements of partially ordered sets; these specify the probabilistic setting of Sachkov's general combinatorial scheme. The author pays special attention to using probabilistic methods to obtain asymptotic formulae that are difficult to derive using combinatorial methods. This was an important book, describing many ideas not previously available in English; the author has taken the chance to rewrite parts of the text and refresh the references where appropriate.

This book develops the combinatorics of Young tableaux and shows them in action in the algebra of symmetric functions, representations of the symmetric and general linear groups, and the geometry of flag varieties. The first part of the book is a self-contained presentation of the basic combinatorics of Young tableaux, including the remarkable constructions of "bumping" and "sliding", and several interesting correspondences. In Part II the author uses these results to study representations with geometry on Grassmannians and flag manifolds, including their Schubert subvarieties, and the related Schubert polynomials. Much of this material has never before appeared in book form. There are numerous exercises throughout, with hints and answers provided. Researchers in representation theory and algebraic geometry as well as in combinatorics will find this book interesting and useful, while students will find the intuitive presentation easy to follow.

The starting point of this book is Sperner's theorem, which answers the question: What is the maximum possible size of a family of pairwise (with respect to inclusion) subsets of a finite set? This theorem stimulated the development of a fast growing theory dealing with external problems on finite sets and, more generally, on finite partially ordered sets. This book presents Sperner theory from a unified point of view, bringing combinatorial techniques together with methods from programming, linear algebra, Lie-algebra representations and eigenvalue methods, probability theory, and enumerative combinatorics. Researchers and graduate students in discrete mathematics, optimisation, algebra, probability theory, number theory, and geometry will find many powerful new methods arising from Sperner theory.

Current research on the spectral theory of finite graphs may be seen as part of a wider effort to forge closer links between algebra and combinatorics (in particular between linear algebra and graph theory).This book describes how this topic can be strengthened by exploiting properties of the eigenspaces of adjacency matrices associated with a graph. The extension of spectral techniques proceeds at three levels: using eigenvectors associated with an arbitrary labelling of graph vertices, using geometrical invariants of eigenspaces such as graph angles and main angles, and introducing certain kinds of canonical eigenvectors by means of star partitions and star bases. One objective is to describe graphs by algebraic means as far as possible, and the book discusses the Ulam reconstruction conjecture and the graph isomorphism problem in this context. Further problems of graph reconstruction and identification are used to illustrate the importance of graph angles and star partitions in relation to graph structure. Specialists in graph theory will welcome this treatment of important new research.

New and striking results obtained in recent years from an intensive study of asymptotic combinatorics have led to a new, higher level of understanding of related problems: the theory of integrable systems, the Riemann-Hilbert problem, asymptotic representation theory, spectra of random matrices, combinatorics of Young diagrams and permutations, and even some aspects of quantum field theory.

This book constitutes the refereed proceedings of the First International Conference on Graph Transformations, ICGT 2002, held in Barcelona, Spain in October 2002.The 26 revised full papers presented were carefully reviewed and selected by the program committe. Also included are abstracts of 3 invited papers, a tutorial, the extended abstract of a tutorial, and 5 reports of workshops held in conjunction with ICGT. The papers deal with various graphical structures that are useful to describe complex systems and computational structures, like graphs, diagrams, visual sentences, and others. Graph transformations are stongly related to graph theory, graph algorithms, formal language and parsing theory, the theory of concurrent and distributed systems, formal specification and verification, and logic and semantics.

This book constitutes the refereed proceedings of the 8th Annual International Computing and Combinatorics Conference, COCOON 2002, held in Singapore in August 2002.The 60 revised full papers presented together with three invited contributions were carefully reviewed and selected from 106 submissions. The papers are organized in topical sections on complexity theory, discrete algorithms, computational biology and learning theory, radio networks, automata and formal languages, Internet networks, computational geometry, combinatorial optimization, and quantum computing.

This volume contains the proceedings of the NATO Advanced Study Institute "Symmetric Functions 2001: Surveys of Developments and Per- spectives", held at the Isaac Newton Institute for Mathematical Sciences in Cambridge, UK, during the two weeks 25 June - 6 July 2001. The objective of the ASI was to survey recent developments and outline research perspectives in various fields, for which the fundamental questions can be stated in the language of symmetric functions (along the way emphasizing interdisciplinary connections). The instructional goals of the event determined its format: the ASI consisted of about a dozen mini-courses. Seven of them served as a basis for the papers comprising the current volume. The ASI lecturers were: Persi Diaconis, William Fulton, Mark Haiman, Phil Hanlon, Alexander Klyachko, Bernard Leclerc, Ian G. Macdonald, Masatoshi Noumi, Andrei Okounkov, Grigori Olshanski, Eric Opdam, Ana- toly Vershik, and Andrei Zelevinsky. The organizing committee consisted of Phil Hanlon, Ian Macdonald, Andrei 0 kounkov, G rigori 0 lshanski (co-director), and myself ( co-director). The original ASI co-director Sergei Kerov, who was instrumental in determining the format and scope of the event, selection of speakers, and drafting the initial grant proposal, died in July 2000. Kerov's mathemat- ical ideas strongly influenced the field, and were presented at length in a number of ASI lectures. A special afternoon session on Monday, July 2, was dedicated to his memory.

In recent years, algorithmic graph theory has become increasingly important as a link between discrete mathematics and theoretical computer science. This textbook introduces students of mathematics and computer science to the interrelated fields of graphs theory, algorithms and complexity.

Originally published in 1996, this is a presentation of some complex problems of discrete mathematics in a simple and unified form using an original, general combinatorial scheme. The author's aim is not always to present the most general results, but rather to focus attention on ones that illustrate the methods described. A distinctive aspect of the book is the large number of asymptotic formulae derived. Professor Sachkov begins with a discussion of block designs and Latin squares before proceeding to treat transversals, devoting much attention to enumerative problems. The main role in these problems is played by generating functions, which are considered in Chapter 3. The general combinatorial scheme is then introduced and in the last chapter Polya's enumerative theory is discussed. This is an important book, describing many ideas not previously available in English; the author has taken the chance to update the text and references where appropriate.

This book constitutes the refereed proceedings of the 7th Annual International Conference on Computing and Combinatorics, COCOON 2001, held in Guilin, China, in August 2001.The 50 revised full papers and 16 short papers presented were carefully reviewed and selected from 97 submissions. The papers are organized in topical sections on complexity theory, computational biology, computational geometry, data structures and algorithms, games and combinatorics, graph algorithms and complexity, graph drawing, graph theory, online algorithms, randomized and average-case algorithms, Steiner trees, systems algorithms and modeling, and computability.

This book constitutes the joint refereed proceedings of the 4th International Workshop on Approximation Algorithms for Optimization Problems, APPROX 2001 and of the 5th International Workshop on Ranomization and Approximation Techniques in Computer Science, RANDOM 2001, held in Berkeley, California, USA in August 2001. The 26 revised full papers presented were carefully reviewed and selected from a total of 54 submissions. Among the issues addressed are design and analysis of approximation algorithms, inapproximability results, on-line problems, randomization, de-randomization, average-case analysis, approximation classes, randomized complexity theory, scheduling, routing, coloring, partitioning, packing, covering, computational geometry, network design, and applications in various fields.

Graph Searching Games and Probabilistic Methods is the first book that focuses on the intersection of graph searching games and probabilistic methods. The book explores various applications of these powerful mathematical tools to games and processes such as Cops and Robbers, Zombie and Survivors, and Firefighting. Written in an engaging style, the book is accessible to a wide audience including mathematicians and computer scientists. Readers will find that the book provides state-of-the-art results, techniques, and directions in graph searching games, especially from the point of view of probabilistic methods. The authors describe three directions while providing numerous examples, which include: * Playing a deterministic game on a random board. * Players making random moves. * Probabilistic methods used to analyze a deterministic game.

50 Years of Combinatorics, Graph Theory, and Computing advances research in discrete mathematics by providing current research surveys, each written by experts in their subjects. The book also celebrates outstanding mathematics from 50 years at the Southeastern International Conference on Combinatorics, Graph Theory & Computing (SEICCGTC). The conference is noted for the dissemination and stimulation of research, while fostering collaborations among mathematical scientists at all stages of their careers. The authors of the chapters highlight open questions. The sections of the book include: Combinatorics; Graph Theory; Combinatorial Matrix Theory; Designs, Geometry, Packing and Covering. Readers will discover the breadth and depth of the presentations at the SEICCGTC, as well as current research in combinatorics, graph theory and computer science. Features: Commemorates 50 years of the Southeastern International Conference on Combinatorics, Graph Theory & Computing with research surveys Surveys highlight open questions to inspire further research Chapters are written by experts in their fields Extensive bibliographies are provided at the end of each chapter

This volume contains the papers presented at the Third Discrete Mathematics and Theoretical Computer Science Conference (DMTCS1), which was held at 'Ovidius'University Constantza, Romania in July 2001.The conference was open to all areas of discrete mathematics and theoretical computer science, and the papers contained within this volume cover topics such as: abstract data types and specifications; algorithms and data structures; automata and formal languages; computability, complexity and constructive mathematics; discrete mathematics, combinatorial computing and category theory; logic, nonmonotonic logic and hybrid systems; molecular computing.