Shortest Connectivity An Introduction with Applications in Phylogeny
The problem of "Shortest Connectivity" has a long and convoluted history: given a finite set of points in a metric space, search for a network that connects these points with the shortest possible length. This shortest network must be a tree and may conta
- PDF / 12,044,755 Bytes
- 277 Pages / 441 x 666 pts Page_size
- 33 Downloads / 171 Views
COMBINATORIAL OPTIMIZATION VOLUME 17 Through monographs and contributed works the objective of the series is to publish state of the art expository research covering all topics in the field of combinatorid optimization. In addition, the series will include books, which are suitable for graduate level courses in computer science, engineering,business, applied mathematics, and operations research. Combinatorial (or discrete) optimization problems arise in various applications, including communications network design, VLSI design, machine vision, airline crew scheduling, corporate planning, computer-aided design and manufacturing, database query design, cellular telephone frequency assignment, constraint directed reasoning, and computational biology. The topics of the books will cover complexity analysis and algorithm design (parallel and serial), computational experiments and application in science and engineering.
Series Editors Ding-Zhu Du, University of Minnesota Panos M . Pardalos, University of Florida
Advisory Editorial Board Alfonso Ferreira, CNRS-LIP ENS London Jun Gu, University of Calgary David S. Johnson, AT&T Research James B. Orlin, MI.T. Christos H . Papadimitriou, University of California at Berkeley Fred S. Roberts, Rutgers University Paul Spirakis, Computer Tech Institute (CTI)
SHORTEST CONNECTIVITY An Introduction with Applications in Phylogeny
DIETMAR CIESLIK Ernst-Moritz-Arndt University, Greifswald, Germany Massey University, Palmerston North, New Zealand
Q - Springer I
Library of Congress Cataloging-in-Publication Data A C.I.P. Catalogue record for this book is available from the Library of Congress.
ISBN 0-387-23538-8
e-ISBN 0-387-23539-6
Printed on acid-free paper.
O 2005 Springer Science+Business Media, Inc. All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, Inc., 233 Spring Street, New York NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now know or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks and similar terms, even if the are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights.
Printed in the United States of America. 9 8 7 6 5 4 3 2 1 springeronline. com
SPIN 11336228
CONTENTS
PREFACE 1
T W O CLASSICAL OPTIMIZATION PROBLEMS 1.1 The Fermat-Torricelli point 1.2 Minimum Spanning Trees
2
GAUSS' QUESTION 2.1 2.2 2.3 2.4 2.5
3
WHAT DOES SOLUTION MEAN? 3.1 3.2 3.3 3.4 3.5
4
,4 metaphysical approach Does a solution exist? Does an algorithm esist? Does an efficient algorithm exist? Does an approximation exist?
NETWORK DESIGN PROBLEMS 4.1 4.2
5
Gauss' question and their coii.i.ersion to Steiner's Problem Examples and Esercises Refe
Data Loading...
