Probabilistic Combinatorial Optimization on Graphs
Published on 1. March 2013
268 pages
978-1-118-61413-6 (ISBN)
Description
This title provides a comprehensive survey over the subject ofprobabilistic combinatorial optimization, discussing probabilisticversions of some of the most paradigmatic combinatorial problems ongraphs, such as the maximum independent set, the minimum vertexcovering, the longest path and the minimum coloring.
Those who possess a sound knowledge of the subject mater willfind the title of great interest, but those who have only somemathematical familiarity and knowledge about complexity andapproximation theory will also find it an accessible andinformative read.
More details
Other editions
Additional editions
Software
01/2010
Wiley
€208.17
No shipping information available
Cecile Murat | Vangelis Th. Paschos
Probabilistic Combinatorial Optimization on Graphs
Book
03/2006
1st Edition
Wiley-ISTE
€164.50
Shipment within 3-4 weeks
Persons
Cécile Murat is Assistant Professor of Computer Scienceat the University of Paris-Dauphine. Her research interests includecombinatorial and probabilistic combinatorial optimization, thedesign and analysis of efficient algorithms and the design ofefficient solutions for hard combinatorial optimization problems.She is the author of over 20 research papers.
Vangelis Th. Paschos is Professor of Computer Science atthe University of Paris-Dauphine and Chairman of the LAMSADE(Laboratory for the Modeling and the Analysis of Decision AidingSystems). His research interests include complexity theory, thetheory of the polynomial approximation of NP-hard problems,probabilistic combinatorial optimization and on-line computation.He is the author of more than a 100 research papers and is a memberof the editorial board of several international scientificjournals.
Content
Preface.
Chapter 1. A Short Insight into Probabilistic Combinatorial Optimization.
Chapter 2. The Probabilistic Maximum Independent Set.
Chapter 3. The Probabilistic Minimum Vertex Cover.
Chapter 4. The Probabilistic Longest Path.
Chapter 5. Probabilistic Minimum Coloring.
Chapter 6. Classification of Probabilistic Graph-problems.
Chapter 7. A Compendium of Probabilistic NPO Problems on Graphs.
Appendix A. Mathematical Preliminaries.
Appendix B. Elements of the Complexity and the Approximation Theory.
Bibliography.
Index.
