Algorithmic graph theory and perfect graphs / / Martin Charles Golumbic |
Autore | Golumbic Martin Charles |
Pubbl/distr/stampa | New York, New York ; ; London, England : , : Academic Press, , 1980 |
Descrizione fisica | 1 online resource (307 p.) |
Disciplina | 511/.5 |
Collana | Computer Science and Applied Mathematics |
Soggetto topico | Perfect graphs |
ISBN | 1-4832-7197-8 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto |
Front Cover; Algorithmic Graph Theory and Perfect Graphs; Copyright Page; Dedication; Table of Contents; Foreword; Preface; Acknowledgments; List of Symbols; Chapter 1. Graph Theoretic Foundations ; 1. Basic Definitions and Notations; 2. Intersection Graphs; 3. Interval Graphs-A Sneak Preview of the Notions Coming Up; 4. Summary; Exercises; Bibliography; Chapter 2. The Design of Efficient Algorithms; 1. The Complexity of Computer Algorithms; 2. Data Structures; 3. How to Explore a Graph; 4. Transitive Tournaments and Topological Sorting; Exercises; Bibliography; Chapter 3. Perfect Graphs
1. The Star of the Show2. The Perfect Graph Theorem; 3. p-Critical and Partitionable Graphs; 4. A Polyhedral Characterization of Perfect Graphs; 5. A Polyhedral Characterization of p-Critical Graphs; 6. The Strong Perfect Graph Conjecture; Exercises; Bibliography; Chapter 4. Triangulated Graphs; 1. Introduction; 2. Characterizing Triangulated Graphs; 3. Recognizing Triangulated Graphs by Lexicographic Breadth-First Search; 4. The Complexity of Recognizing Triangulated Graphs; 5. Triangulated Graphs as Intersection Graphs; 6. Triangulated Graphs Are Perfect 7. Fast Algorithms for the COLORING, CLIQUE, STABLE SET, and CLIQUE-COVER Problems on Triangulated GraphsExercises; Bibliography; Chapter 5. Comparability Graphs; 1. Γ-Chains and Implication Classes; 2. Uniquely Partially Orderable Graphs; 3. The Number of Transitive Orientations; 4. Schemes and G-Decompositions-An Algorithm for Assigning Transitive Orientations; 5. The Γ*-Matroid of a Graph; 6. The Complexity of Comparability Graph Recognition; 7. Coloring and Other Problems on Comparability Graphs; 8. The Dimension of Partial Orders; Exercises; Bibliography; Chapter 6. Split Graphs 1. An Introduction to Chapters 6-8: Interval, Permutation, and Split Graphs2. Characterizing Split Graphs; 3. Degree Sequences and Split Graphs; Exercises; Bibliography; Chapter 7. Permutation Graphs; 1. Introduction; 2. Characterizing Permutation Graphs; 3. Permutation Labelings; 4. Applications; 5. Sorting a Permutation Using Queues in Parallel; Exercises; Bibliography; Chapter 8. Interval Graphs; 1. How It All Started; 2. Some Characterizations of Interval Graphs; 3. The Complexity of Consecutive 1's Testing; 4. Applications of Interval Graphs; 5. Preference and Indifference 6. Circular-Arc GraphsExercises; Bibliography; Chapter 9. Superperfect Graphs; 1. Coloring Weighted Graphs; 2. Superperfection; 3. An Infinite Class of Superperfect Noncomparability Graphs; 4. When Does Superperfect Equal Comparability?; 5. Composition of Superperfect Graphs; 6. A Representation Using the Consecutive 1's Property; Exercises; Bibliography; Chapter 10. Threshold Graphs; 1. The Threshold Dimension; 2. Degree Partition of Threshold Graphs; 3. A Characterization Using Permutations; 4. An Application to Synchronizing Parallel Processes; Exercises; Bibliography Chapter 11. Not So Perfect Graphs |
Record Nr. | UNINA-9910786640403321 |
Golumbic Martin Charles | ||
New York, New York ; ; London, England : , : Academic Press, , 1980 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Algorithmic graph theory and perfect graphs / / Martin Charles Golumbic |
Autore | Golumbic Martin Charles |
Pubbl/distr/stampa | New York, New York ; ; London, England : , : Academic Press, , 1980 |
Descrizione fisica | 1 online resource (307 p.) |
Disciplina | 511/.5 |
Collana | Computer Science and Applied Mathematics |
Soggetto topico | Perfect graphs |
ISBN | 1-4832-7197-8 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto |
Front Cover; Algorithmic Graph Theory and Perfect Graphs; Copyright Page; Dedication; Table of Contents; Foreword; Preface; Acknowledgments; List of Symbols; Chapter 1. Graph Theoretic Foundations ; 1. Basic Definitions and Notations; 2. Intersection Graphs; 3. Interval Graphs-A Sneak Preview of the Notions Coming Up; 4. Summary; Exercises; Bibliography; Chapter 2. The Design of Efficient Algorithms; 1. The Complexity of Computer Algorithms; 2. Data Structures; 3. How to Explore a Graph; 4. Transitive Tournaments and Topological Sorting; Exercises; Bibliography; Chapter 3. Perfect Graphs
1. The Star of the Show2. The Perfect Graph Theorem; 3. p-Critical and Partitionable Graphs; 4. A Polyhedral Characterization of Perfect Graphs; 5. A Polyhedral Characterization of p-Critical Graphs; 6. The Strong Perfect Graph Conjecture; Exercises; Bibliography; Chapter 4. Triangulated Graphs; 1. Introduction; 2. Characterizing Triangulated Graphs; 3. Recognizing Triangulated Graphs by Lexicographic Breadth-First Search; 4. The Complexity of Recognizing Triangulated Graphs; 5. Triangulated Graphs as Intersection Graphs; 6. Triangulated Graphs Are Perfect 7. Fast Algorithms for the COLORING, CLIQUE, STABLE SET, and CLIQUE-COVER Problems on Triangulated GraphsExercises; Bibliography; Chapter 5. Comparability Graphs; 1. Γ-Chains and Implication Classes; 2. Uniquely Partially Orderable Graphs; 3. The Number of Transitive Orientations; 4. Schemes and G-Decompositions-An Algorithm for Assigning Transitive Orientations; 5. The Γ*-Matroid of a Graph; 6. The Complexity of Comparability Graph Recognition; 7. Coloring and Other Problems on Comparability Graphs; 8. The Dimension of Partial Orders; Exercises; Bibliography; Chapter 6. Split Graphs 1. An Introduction to Chapters 6-8: Interval, Permutation, and Split Graphs2. Characterizing Split Graphs; 3. Degree Sequences and Split Graphs; Exercises; Bibliography; Chapter 7. Permutation Graphs; 1. Introduction; 2. Characterizing Permutation Graphs; 3. Permutation Labelings; 4. Applications; 5. Sorting a Permutation Using Queues in Parallel; Exercises; Bibliography; Chapter 8. Interval Graphs; 1. How It All Started; 2. Some Characterizations of Interval Graphs; 3. The Complexity of Consecutive 1's Testing; 4. Applications of Interval Graphs; 5. Preference and Indifference 6. Circular-Arc GraphsExercises; Bibliography; Chapter 9. Superperfect Graphs; 1. Coloring Weighted Graphs; 2. Superperfection; 3. An Infinite Class of Superperfect Noncomparability Graphs; 4. When Does Superperfect Equal Comparability?; 5. Composition of Superperfect Graphs; 6. A Representation Using the Consecutive 1's Property; Exercises; Bibliography; Chapter 10. Threshold Graphs; 1. The Threshold Dimension; 2. Degree Partition of Threshold Graphs; 3. A Characterization Using Permutations; 4. An Application to Synchronizing Parallel Processes; Exercises; Bibliography Chapter 11. Not So Perfect Graphs |
Record Nr. | UNINA-9910811710303321 |
Golumbic Martin Charles | ||
New York, New York ; ; London, England : , : Academic Press, , 1980 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Tolerance graphs / / Martin Charles Golumbic, Ann N. Trenk [[electronic resource]] |
Autore | Golumbic Martin Charles |
Pubbl/distr/stampa | Cambridge : , : Cambridge University Press, , 2004 |
Descrizione fisica | 1 online resource (xii, 265 pages) : digital, PDF file(s) |
Disciplina | 511.5 |
Collana | Cambridge studies in advanced mathematics |
Soggetto topico | Graph theory |
ISBN |
1-107-14728-X
1-280-44950-0 9786610449507 0-511-18563-4 0-511-18480-8 0-511-18745-9 0-511-31356-X 0-511-54298-4 0-511-18652-5 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Introduction -- Early work on tolerance graphs -- Trees, cotrees and bipartite graphs -- Interval probe graphs -- Bitolerance graphs and ordered sets -- Unit and 50% tolerance graphs -- Comparability and invariance results -- Bounded bitolerance recognition -- Algorithms on tolerance graphs -- The hierarchy of bitolerance orders -- Tolerance models on trees -- Phi-tolerance models -- Directed tolerance graphs -- Open questions and further directions. |
Record Nr. | UNINA-9910457917403321 |
Golumbic Martin Charles | ||
Cambridge : , : Cambridge University Press, , 2004 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Tolerance graphs / / Martin Charles Golumbic, Ann N. Trenk [[electronic resource]] |
Autore | Golumbic Martin Charles |
Pubbl/distr/stampa | Cambridge : , : Cambridge University Press, , 2004 |
Descrizione fisica | 1 online resource (xii, 265 pages) : digital, PDF file(s) |
Disciplina | 511.5 |
Collana | Cambridge studies in advanced mathematics |
Soggetto topico | Graph theory |
ISBN |
1-107-14728-X
1-280-44950-0 9786610449507 0-511-18563-4 0-511-18480-8 0-511-18745-9 0-511-31356-X 0-511-54298-4 0-511-18652-5 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Introduction -- Early work on tolerance graphs -- Trees, cotrees and bipartite graphs -- Interval probe graphs -- Bitolerance graphs and ordered sets -- Unit and 50% tolerance graphs -- Comparability and invariance results -- Bounded bitolerance recognition -- Algorithms on tolerance graphs -- The hierarchy of bitolerance orders -- Tolerance models on trees -- Phi-tolerance models -- Directed tolerance graphs -- Open questions and further directions. |
Record Nr. | UNINA-9910784438503321 |
Golumbic Martin Charles | ||
Cambridge : , : Cambridge University Press, , 2004 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Tolerance graphs / / Martin Charles Golumbic, Ann N. Trenk [[electronic resource]] |
Autore | Golumbic Martin Charles |
Pubbl/distr/stampa | Cambridge : , : Cambridge University Press, , 2004 |
Descrizione fisica | 1 online resource (xii, 265 pages) : digital, PDF file(s) |
Disciplina | 511.5 |
Collana | Cambridge studies in advanced mathematics |
Soggetto topico | Graph theory |
ISBN |
1-107-14728-X
1-280-44950-0 9786610449507 0-511-18563-4 0-511-18480-8 0-511-18745-9 0-511-31356-X 0-511-54298-4 0-511-18652-5 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Introduction -- Early work on tolerance graphs -- Trees, cotrees and bipartite graphs -- Interval probe graphs -- Bitolerance graphs and ordered sets -- Unit and 50% tolerance graphs -- Comparability and invariance results -- Bounded bitolerance recognition -- Algorithms on tolerance graphs -- The hierarchy of bitolerance orders -- Tolerance models on trees -- Phi-tolerance models -- Directed tolerance graphs -- Open questions and further directions. |
Record Nr. | UNINA-9910828052703321 |
Golumbic Martin Charles | ||
Cambridge : , : Cambridge University Press, , 2004 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
The zeroth book of graph theory : an annotated translation of of "Les réseaux (ou graphes)"André Sainte-Laguë (1926) / / Martin Charles Golumbic, André Sainte-Laguë |
Autore | Golumbic Martin Charles |
Edizione | [1st ed. 2021.] |
Pubbl/distr/stampa | Cham, Switzerland : , : Springer, , [2021] |
Descrizione fisica | 1 online resource (XII, 122 p. 24 illus., 3 illus. in color.) |
Disciplina | 511.5 |
Collana | History of Mathematics Subseries |
Soggetto topico |
Discrete mathematics
Graph theory Operations Research, Management Science |
ISBN | 3-030-61420-4 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Foreword -- Preface -- Tracing the topics in Les Réseaux (ou Graphes) -- Networks (or Graphs)— André Sainte-Laguë (1926) -- I Introduction and definitions -- II Trees -- III Chains and cycles -- IV Regular graphs -- V Cubic graphs -- VI Tableaux -- VII Hamiltonian graphs -- VIII Chessboard problems -- X Conclusion -- A short biography of André Sainte-Laguë -- Biography of Guy Ghidale Iliovici -- Bibliography -- Index -- Glossary -- Acknowledgements -- Martin Charles Golumbic. |
Record Nr. | UNISA-996466549603316 |
Golumbic Martin Charles | ||
Cham, Switzerland : , : Springer, , [2021] | ||
Materiale a stampa | ||
Lo trovi qui: Univ. di Salerno | ||
|
The zeroth book of graph theory : an annotated translation of of "Les réseaux (ou graphes)"André Sainte-Laguë (1926) / / Martin Charles Golumbic, André Sainte-Laguë |
Autore | Golumbic Martin Charles |
Edizione | [1st ed. 2021.] |
Pubbl/distr/stampa | Cham, Switzerland : , : Springer, , [2021] |
Descrizione fisica | 1 online resource (XII, 122 p. 24 illus., 3 illus. in color.) |
Disciplina | 511.5 |
Collana | History of Mathematics Subseries |
Soggetto topico |
Discrete mathematics
Graph theory Operations Research, Management Science |
ISBN | 3-030-61420-4 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Foreword -- Preface -- Tracing the topics in Les Réseaux (ou Graphes) -- Networks (or Graphs)— André Sainte-Laguë (1926) -- I Introduction and definitions -- II Trees -- III Chains and cycles -- IV Regular graphs -- V Cubic graphs -- VI Tableaux -- VII Hamiltonian graphs -- VIII Chessboard problems -- X Conclusion -- A short biography of André Sainte-Laguë -- Biography of Guy Ghidale Iliovici -- Bibliography -- Index -- Glossary -- Acknowledgements -- Martin Charles Golumbic. |
Record Nr. | UNINA-9910739404603321 |
Golumbic Martin Charles | ||
Cham, Switzerland : , : Springer, , [2021] | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|