Introduction to Graph Convexity

• Verfasst von: Araújo, Júlio [VerfasserIn]
• Verfasst von: Dourado, Mitre C. [VerfasserIn]
• Verfasst von: Protti, Fábio [VerfasserIn]
• Verfasst von: Sampaio, Rudini M. [VerfasserIn]
• Titel: Introduction to Graph Convexity
• Titelzusatz: An Algorithmic Approach
• Verf.angabe: by Júlio Araújo, Mitre C. Dourado, Fábio Protti, Rudini M. Sampaio
• Ausgabe: 1st ed. 2025.
• Verlagsort: Cham
• Verlagsort: Cham
• Verlag: Springer Nature Switzerland
• Verlag: Imprint: Springer
• E-Jahr: 2025
• Jahr: 2025.
• Jahr: 2025.
• Umfang: 1 Online-Ressource(XV, 152 p. 47 illus., 20 illus. in color.)
• Gesamttitel/Reihe: SBMAC Collection on Applied and Computational Mathematics
• ISBN: 978-3-031-84128-6
• DOI: doi:10.1007/978-3-031-84128-6
• Datenträger: Online-Ressource
• Sprache: eng
• Bibliogr. Hinweis: Erscheint auch als : Druck-Ausgabe
• Bibliogr. Hinweis: Erscheint auch als : Druck-Ausgabe
• Bibliogr. Hinweis: Erscheint auch als : Druck-Ausgabe
• K10plus-PPN: 1926116828
• K10plus-PPN:
  Universitätsbibliothek
• Lokale URL UB: Zum Volltext

Abstract

Part I Fundamentals of Convexity in Graphs -- Basic Concepts of Convexity -- Convexity in Graphs -- Graph Convexity Parameters -- Convex Geometries in Graphs -- Part II Main Convexities and Applications -- P3 and P3* Convexities -- Geodesic Convexity -- Other Convexities -- Convexity in Oriental Graphs -- Applications in Graph Convexities.

Abstract

This book focuses on the computational aspects of graph convexity, with a particular emphasis on path convexity within graphs. It provides a thoughtful introduction to this emerging research field, which originated by adapting concepts from convex geometry to combinatorics and has experienced substantial growth. The book starts with an introduction of fundamental convexity concepts and then proceeds to discuss convexity parameters. These parameters fall into two categories: one derived from abstract convexity studies and another motivated by computational complexity. Subsequent chapters explore geometric convexity within graphs, examining various graph classes such as interval graphs, proper interval graphs, cographs, chordal graphs, and strongly chordal graphs. The text concludes with a study of the computation of convexity parameters across different convexity types, including practical applications in areas like game theory. Compact and straightforward, this work serves as an ideal entry point for students and researchers interested in pursuing further research in the field of convexity. The English translation of this book, originally in Portuguese, was facilitated by artificial intelligence. The content was later revised by the authors for accuracy.