Antimatroids, Betweenness, Convexity
Two classical examples of antimatroids arise from double shellings of partially ordered sets and from simplicial shellings of triangulated graphs. The corresponding convex geometries have Carathéodory number two and admit a natural description in terms of
- PDF / 6,620,153 Bytes
- 565 Pages / 439.37 x 666.142 pts Page_size
- 103 Downloads / 168 Views
William J. Cook · László Lovász · Jens Vygen Editors
Research Trends in Combinatorial Optimization Bonn 2008
William Cook Industrial and Systems Engineering Georgia Tech 765 Ferst Drive Atlanta, Georgia 30332-0205 USA [email protected]
László Lovász Eötvös Loránd University Institute of Mathematics Pázmány Péter sétány 1/C H-1117 Budapest Hungary [email protected]
Jens Vygen Research Institute for Discrete Mathematics University of Bonn Lennéstr. 2 53113 Bonn Germany [email protected]
ISBN 978-3-540-76795-4
e-ISBN 978-3-540-76796-1
DOI 10.1007/978-3-540-76796-1 Library of Congress Control Number: 2008932935 Mathematics Subject Classification (2000): 90CXX © 2009 Springer-Verlag Berlin Heidelberg This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Cover design: WMXDesign GmbH Printed on acid-free paper 9 8 7 6 5 4 3 2 1 springer.com
Dedicated to Bernhard Korte
Preface
The editors and authors dedicate this book to Bernhard Korte on the occasion of his seventieth birthday. We, the editors, are happy about the overwhelming feedback to our initiative to honor him with this book and with a workshop in Bonn on November 3–7, 2008. Although this would be a reason to look back, we would rather like to look forward and see what are the interesting research directions today. This book is written by leading experts in combinatorial optimization. All papers were carefully reviewed, and eventually twenty-three of the invited papers were accepted for this book. The breadth of topics is typical for the field: combinatorial optimization builds bridges between areas like combinatorics and graph theory, submodular functions and matroids, network flows and connectivity, approximation algorithms and mathematical programming, computational geometry and polyhedral combinatorics. All these topics are related, and they are all addressed in this book. Combinatorial optimization is also known for its numerous applications. To limit the scope, however, this book is not primarily about applications, although some are mentioned at various places. Most papers in this volume are surveys that provide an excellent overview of an active research area, but this book also contains many new results. Highlighting many of the currently most interestin
Data Loading...
