E-Book Overview
This title provides a comprehensive survey over the subject of probabilistic combinatorial optimization, discussing probabilistic versions of some of the most paradigmatic combinatorial problems on graphs, such as the maximum independent set, the minimum vertex covering, the longest path and the minimum coloring.
Those who possess a sound knowledge of the subject mater will find the title of great interest, but those who have only some mathematical familiarity and knowledge about complexity and approximation theory will also find it an accessible and informative read.
E-Book Content
Probabilistic Combinatorial Optimization on Graphs This page intentionally left blank Probabilistic Combinatorial Optimization on Graphs Cécile Murat and Vangelis Th. Paschos First published in Great Britain and the United States in 2006 by ISTE Ltd Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address: ISTE Ltd 6 Fitzroy Square London W1T 5DX UK ISTE USA 4308 Patrice Road Newport Beach, CA 92663 USA www.iste.co.uk © ISTE Ltd, 2006 The rights of Cécile Murat and Vangelis Th. Paschos to be identified as the authors of this work has been asserted by them in accordance with the Copyright, Designs and Patents Act 1988. Library of Congress Cataloging-in-Publication Data Murat, Cecile. Probabilistic combinatorial optimization on graphs / Cécile Murat and Vangelis Th. Pascho