Hamiltonian Cycle Problem and Markov Chains
This research monograph summarizes a line of research that maps certain classical problems of discrete mathematics and operations research - such as the Hamiltonian cycle and the Travelling Salesman problems – into convex domains where continuum analysis
- PDF / 2,667,075 Bytes
- 205 Pages / 439.37 x 666.142 pts Page_size
- 40 Downloads / 211 Views
Volume 171
Series Editor: Frederick S. Hillier Stanford University, CA, USA Special Editorial Consultant: Camille C. Price Stephen F. Austin State University, TX, USA
For further volumes www.springer.com/series/6161
Vivek S. Borkar • Vladimir Ejov • Jerzy A. Filar Giang T. Nguyen
Hamiltonian Cycle Problem and Markov Chains
1C
Professor Vivek S. Borkar Department of Electrical Engineering, IIT, Powai, Mumbai 400076, India Associate Professor Vladimir Ejov Flinders Mathematical Sciences Laboratory School of Computer Science, Engineering and Mathematics Flinders University Bedford Park, SA 5042, Australia
Professor Jerzy A. Filar Flinders Mathematical Sciences Laboratory School of Computer Science, Engineering and Mathematics Flinders University Bedford Park, SA 5042, Australia Dr Giang T. Nguyen Département d’Informatique Université libre de Bruxelles CP 212, Boulevard du Triomphe, 2, 1050 Brussels, Belgium
ISSN 0884-8289 ISBN 978-1-4614-3231-9 ISBN 978-1-4614-3232-6 (eBook) DOI 10.1007/978-1-4614-3232-6 Springer New York Dordrecht Heidelberg London Library of Congress Control Number: 2012933371 © Springer Science+Business Media, LLC 2012 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, LLC, 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 known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they 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 on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)
To the new generation of mathematicians from developing countries who will, undoubtedly, have a profound influence on the discipline in the coming decades.
Preface
Graphs and networks have been studied extensively in recent decades by mathematicians, computer scientists, engineers, operations researchers as well as physicists, biologists, chemists, and even linguists and sociologists. Their two key elements, vertices and edges, are extremely useful as representations of a wide spectrum of phenomena ranging from transportation networks, through topology of atoms to social networks. Furthermore, many problems modelled with graphs and networks naturally lend themselves to algorithmic analysis and ultimate solutions with the help of modern high-speed computers. The shortest path, maximal spanning tree and max-flow/min-cut problems are just three examples out of a large collection of well-solved important problems. Nonetheless, there is also a large collection of graph theoretic and network optimisation problems that are fundamentally difficult in the sense of belon
Data Loading...
