Algorithms and Combinatorics

Sparsity

Graphs, Structures, and Algorithms

Authors: Nešetřil, Jaroslav, Ossona de Mendez, Patrice

  • One of the first textbooks on the topic of sparsity - a core area of current discrete mathematics
  • Extremely useful to both mathematicians and computer scientists
  • Pedagogically excellent
see more benefits

Buy this book

eBook $59.99
price for USA (gross)
  • ISBN 978-3-642-27875-4
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover $79.95
price for USA
  • ISBN 978-3-642-27874-7
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Softcover $79.95
price for USA
  • ISBN 978-3-642-42776-3
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Rent the ebook  
  • Rental duration: 1 or 6 month
  • low-cost access
  • online reader with highlighting and note-making option
  • can be used across all devices
About this Textbook

This is the first book devoted to the systematic study of sparse graphs and sparse finite structures. Although the notion of sparsity appears in various contexts and is a typical example of a hard to define notion, the authors devised an unifying classification of general classes of structures. This approach is very robust and it has many remarkable properties. For example the classification is expressible in many different ways involving most extremal combinatorial invariants.

This study of sparse structures found applications in such diverse areas as algorithmic graph theory, complexity of algorithms, property testing, descriptive complexity and mathematical logic (homomorphism preservation,fixed parameter tractability and constraint satisfaction problems). It should be stressed that despite of its generality this approach leads to linear (and nearly linear) algorithms.

Jaroslav Nešetřil is a professor at Charles University, Prague; Patrice Ossona de Mendez is a CNRS researcher et EHESS, Paris.

This book is related to the material presented by the first author at ICM 2010.

Reviews

From the reviews:

“This well-crafted and well-written work … brings the authors’ vast knowledge, expertise, taste, and judgment to bear on an increasingly important and mainstream subject. … This is a much-needed book devoted to the systematic study of sparse graphs and sparse classes of structures. … This is an important and useful book. It contains a wealth of up-to-date material, some of which is not readily available in research papers. … A researcher in graph theory or related fields will find this an excellent reference work.” (József Balogh, Mathematical Reviews, March, 2013)

“This is an excellent and useful book for all researchers in mathematics, computer science, logic, and even in any field in physical science, who seek the tools available for analysis of the properties of discrete structures, and particularly, sparse structures.” (Tadashi Sakuma, zbMATH, Vol. 1268, 2013)

“The book is very well written and diagrammed to beautifully present the theory supporting the study of sparse and dense objects. … the book contains up-to-date research topics laid out in an amazing chain of thoughts. Almost every chapter ends with exercises, aiding professors in advanced graduate courses. The extensive list of references, together with conjectures and open problems, offers professors, students, and researchers … profound knowledge on the sparsity of graphs, all in one great book.” (Andre Maximo, Computing Reviews, October, 2012)

Table of contents (20 chapters)

Buy this book

eBook $59.99
price for USA (gross)
  • ISBN 978-3-642-27875-4
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover $79.95
price for USA
  • ISBN 978-3-642-27874-7
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Softcover $79.95
price for USA
  • ISBN 978-3-642-42776-3
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Rent the ebook  
  • Rental duration: 1 or 6 month
  • low-cost access
  • online reader with highlighting and note-making option
  • can be used across all devices
Loading...

Recommended for you

Loading...

Bibliographic Information

Bibliographic Information
Book Title
Sparsity
Book Subtitle
Graphs, Structures, and Algorithms
Authors
Series Title
Algorithms and Combinatorics
Series Volume
28
Copyright
2012
Publisher
Springer-Verlag Berlin Heidelberg
Copyright Holder
Springer-Verlag Berlin Heidelberg
eBook ISBN
978-3-642-27875-4
DOI
10.1007/978-3-642-27875-4
Hardcover ISBN
978-3-642-27874-7
Softcover ISBN
978-3-642-42776-3
Series ISSN
0937-5511
Edition Number
1
Number of Pages
XXIII, 459
Number of Illustrations and Tables
32 b/w illustrations, 100 illustrations in colour
Topics