Graphs, Dioids and Semirings: New Models and Algorithms

Front Cover
Springer Science & Business Media, May 14, 2008 - Business & Economics - 388 pages

The primary objective of this essential text is to emphasize the deep relations existing between the semiring and dio´d structures with graphs and their combinatorial properties. It does so at the same time as demonstrating the modeling and problem-solving flexibility of these structures. In addition the book provides an extensive overview of the mathematical properties employed by "nonclassical" algebraic structures which either extend usual algebra or form a new branch of it.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

PreSemirings Semirings and Dioids
1
2 Semigroups and Monoids
3
22 Combinatorial Properties of Finite Semigroups
6
23 Cancellative Monoids and Groups
7
3 Ordered Monoids
9
Examples
11
33 Canonical Preorder in a Commutative Monoid
12
34 Canonically Ordered Monoids
13
63 The Maximum Capacity Path Problem and the Minimum Spanning Tree Problem
159
65 The Shortest Path Problem
160
68 The Kth Shortest Path Problem
161
69 The Network Reliability Problem
163
610 The ηOptimal Path Problem
164
611 The Multiplier Effect in Economy
165
613 Fuzzy Graphs and Relations
166
614 The Algebraic Structure of Hierarchical Clustering
167

35 HemiGroups
17
37 Classification of Monoids
20
42 PreSemirings
22
5 Semirings
23
52 Rings and Fields
24
53 The Absorption Property in PreSemiRings
25
54 Product of Semirings
26
6 Dioids
28
62 Dioid of Endomorphisms of a Canonically Ordered Commutative Monoid
31
63 Symmetrizable Dioids
33
65 DoublyIdempotent Dioids and Distributive Lattices DoublySelective Dioids
34
66 IdempotentCancellative Dioids SelectiveCancellative Dioids
36
67 IdempotentInvertible Dioids SelectiveInvertible Dioids
37
68 Product of Dioids
38
69 Dioid Canonically Associated with a Semiring
39
610 Classification of Dioids
40
Combinatorial Properties of PreSemirings
51
2 Polynomials and Formal Series with Coefficients in a Pre Semiring
52
22 Formal Series
54
4 Bideterminant of a Square Matrix Characteristic Bipolynomial
55
41 Reminder About Permutations
56
42 Bideterminant of a Matrix
58
43 Characteristic Bipolynomial
59
5 Bideterminant of a Matrix Product as a Combinatorial Property of PreSemirings
61
6 CayleyHamilton Theorem in PreSemirings
65
7 Semirings Bideterminants and Arborescences
69
72 Proof of Extended Theorem
70
73 The Classical MatrixTree Theorem as a Special Case
74
74 A Still More General Version of the Theorem
75
8 A Generalization of the Mac Mahon Identity to Commutative PreSemirings
76
81 The Generalized Mac Mahon Identity
77
82 The Classical Mac Mahon Identity as a Special Case
79
Topology on Ordered Sets Topological Dioids
83
21 The SupTopology
84
22 The InfTopology
85
3 Convergence in the SupTopology and Upper Bound
86
32 Concepts of Limitsup and Limitinf
88
4 Continuity of Functions SemiContinuity
89
5 The FixedPoint Theorem in an Ordered Set
90
6 Topological Dioids
91
QuasiInverse
93
7 PStable Elements in a Dioid
97
71 Examples
98
72 Solving Linear Equations
100
73 Solving Nonlinear Equations
103
8 Residuation and Generalized Solutions
107
Solving Linear Systems in Dioids
115
2 The Shortest Path Problem as a Solution to a Linear System in a Dioid
116
22 Bellmans Algorithm and Connection with Jacobis Method
118
24 Minimality of BellmanJacobi Solution
119
3 QuasiInverse of a Matrix with Elements in a Semiring Existence and Properties
120
32 Graph Associated with a Matrix Generalized Adjacency Matrix and Associated Properties
121
33 Conditions for Existence of the QuasiInverse A
125
34 QuasiInverse and Solutions of Linear Systems Minimality for Dioids
127
4 Iterative Algorithms for Solving Linear Systems
129
42 Generalized GaussSeidel Algorithm
130
43 Generalized Dijkstra Algorithm Greedy Algorithm in Some Selective Dioids
133
44 Extensions of Iterative Algorithms to Algebras of Endomorphisms
136
Generalized GaussJordan Method and Variations
145
Algorithms
151
53 Generalized Escalator Method
152
An Overview of Pathfinding Problems in Graphs
156
61 Problems of Existence and Connectivity
158
Linear Dependence and Independence in SemiModules and Moduloids
173
22 Morphisms of SemiModules or Moduloids Endomorphisms
175
23 SubSemiModule Quotient SemiModule
176
25 Concept of Linear Dependence and Independence in SemiModules
177
3 Bideterminant and Linear Independence
181
31 Permanent Bideterminant and Alternating Linear Mappings
182
General Results
184
The Case of Selective Dioids
187
34 Bideterminant and Linear Independence in SelectiveInvertible Dioids
192
35 Bideterminant and Linear Independence in MaxMin or MinMax Dioids
200
Eigenvalues and Eigenvectors of Endomorphisms
207
General Results
208
3 Eigenvalues and Eigenvectors in Idempotent Dioids
212
4 Eigenvalues and Eigenvectors in Dioids with Multiplicative Group Structure
220
42 The PerronFrobenius Theorem for Some SelectiveInvertible Dioids
227
5 Eigenvalues Bideterminant and Characteristic Bipolynomial
231
6 Applications in Data Analysis
233
61 Applications in Hierarchical Clustering
234
A Few Answers to the Condorcet Paradox
238
Dynamic Linear System Theory
242
71 Classical Linear Dynamic Systems in Automation
243
72 Dynamic Scheduling Problems
244
74 Timed Event Graphs and Their Linear Representation in R Max+ and R +min+
247
75 Eigenvalues and Maximum Throughput of an Autonomous System
251
Dioids and Nonlinear Analysis
257
2 MINPLUS Analysis
261
3 Wavelets in MINPLUS Analysis
268
4 InfConvergence in MINPLUS Analysis
271
5 Weak Solutions in MINPLUS Analysis Viscosity Solutions
278
6 Explicit Solutions to Nonlinear PDEs in MINPLUS Analysis
283
The HopfLax Formula
288
7 MINMAX Analysis
291
72 InfConvergence in MINMAX Analysis
293
73 Explicit Solutions to Nonlinear PDEs in MINMAX Analysis
294
74 Eigenvalues and Eigenf unctions for Endomorphisms in MINMAX Analysis
295
8 The Cramer Transform
298
Collected Examples of Monoids PreSemirings and Dioids
313
11 General Monoids
314
12 Groups
318
13 Canonically Ordered Monoids
319
14 HemiGroups
323
15 Idempotent Monoids SemiLattices
325
16 Selective Monoids
328
2 PreSemirings and PreDioids
331
21 Right or Left PreSemirings and PreDioids
332
22 PreSemiring of Endomorphisms of a Commutative Monoid
335
23 PreSemiring Product of a PreDioid and a Ring
336
24 PreDioids
337
3 Semirings and Rings
338
31 General Semirings
339
32 Rings
340
4 Dioids
341
42 Dioid of Endomorphisms of a Canonically Ordered Commutative Monoid Examples
345
43 General Dioids
348
44 Symmetrizable Dioids
351
45 Idempotent Dioids
353
46 Doubly Idempotent Dioids Distributive Lattices
357
47 IdempotentCancellative and SelectiveCancellative Dioids
358
48 IdempotentInvertible and SelectiveInvertible Dioids
361
References
367
Index
377
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information