Graph Theory, Computational Intelligence and Thought

Cover Page
......Page 1
Title Page
......Page 2
When I Was Seventeen, It Was a Very Good Year…......Page 12
When I Was Twenty One, It Was a Very Good Year…......Page 17
When I Was Thirty Five, It Was a Very Good Year…......Page 20
But Now the Days Are Short…......Page 24
Introduction......Page 26
Port Graph Rewriting......Page 27
The Port Graph Rewriting Calculus......Page 30
Reduction Semantics......Page 31
Strategies as Abstractions......Page 32
Persistent Strategies......Page 33
Embedding Runtime Verification......Page 34
References......Page 36
Introduction......Page 38
Algorithm for a Clique Intersecting All Maximum Independent Sets......Page 40
Minimum Dominating Holes......Page 42
Algorithm for a Maximum Induced Split Subgraph......Page 44
References......Page 46
Basic Concepts......Page 47
The Nested Graph Recognition Algorithm......Page 49
References......Page 51
Introduction......Page 52
The Model......Page 53
The (Non)-Existence of a Potential Function......Page 54
ACGs with $n$>2 Players or $m$>2 Resources......Page 55
The Single Profitable Move Property......Page 57
Stability Under Single Moves......Page 58
One- and Two-Step Additions......Page 59
Post-Addition D-Stability......Page 60
Computation of a Pure Strategy Nash Equilibrium......Page 61
References......Page 63
Introduction......Page 65
Preliminaries......Page 66
Definite Horn Formulas with Size-2 Clauses......Page 67
Small Formulas with All Implicates......Page 68
Duplicates and Escher Configurations......Page 70
No Resolvents of Size 3......Page 71
No Resolvents of Size 4......Page 72
Random Formulas......Page 73
Further Comments......Page 74
References......Page 75
Introduction......Page 77
Algorithm MAP-CHILDREN for Forest Vertex-Cover......Page 79
Algorithm MAP-LEAVES for Forest Vertex-Cover......Page 81
Algorithms for Maximum Packing of a Forest in a Tree......Page 83
Covering the Edges by a Minimum Ordered or Unordered Forest Edge-Cover......Page 84
An algorithm for a Minimum Consecutive Forest Edge-Cover......Page 85
References......Page 87
Introduction......Page 88
An NP-Completeness Result......Page 90
Dominating Induced Matchings in Claw-Free Graphs......Page 91
Concluding Remarks......Page 96
References......Page 97
Introduction......Page 98
HyperConsistency Width......Page 101
Links with Projective Width......Page 103
Acyclic HyperConsistency Width......Page 104
Links with Generalized Hypertree Width......Page 105
Complexity Results on No-Promise Problems......Page 106
Discussion and Conclusion......Page 109
References......Page 110
Introduction......Page 111
Multi-dimensionwise Variation......Page 112
Variable Opt......Page 113
Other Algorithms......Page 115
Random Instance Family......Page 116
Composite Instance Family......Page 118
Experiment Results......Page 119
Single Run Experiments......Page 120
Repetitive Search Experiments......Page 121
References......Page 125
Introduction......Page 127
Basic Notions......Page 129
The Maximum Distance-3 Matching Problem for Chordal Graphs Is NP-Complete......Page 131
Strongly Chordal Graphs, Ptolemaic Graphs and Interval Graphs......Page 132
Combining Clique Separators, Modular Decomposition and the Antineighborhood Approach......Page 133
The Maximum Distance-$k$ Matching Problem for AT-Free Graphs, (Claw,Net)-Free Graphs and Some Other Subclasses of Claw-Free Graphs......Page 134
References......Page 135
Introduction......Page 138
Maximum Matchings and Local Maximum Stable Sets......Page 140
References......Page 143
Introduction......Page 145
Preliminaries and the Main Result......Page 146
Outline of Proof......Page 148
Details of Proof......Page 149
When $G$ Is Not Acyclic......Page 152
References......Page 153
Introduction......Page 155
Graphs without Cycles of Length 4 and 6......Page 156
References......Page 158
On the Cubicity of AT-Free Graphs and Circular-Arc Graphs......Page 159
Introduction......Page 160
Our Results......Page 161
The Construction......Page 162
Applying Our Results......Page 165
References......Page 168
Introduction......Page 169
Split Sets and Split Decomposition Trees......Page 170
The Strategy......Page 173
Implementation of $S(a, b, G) and L(a, b, c, G)$......Page 175
The $O(m log n)$ Time Bound......Page 177
What Goes Wrong If $G$ Is Not Strongly-Connected......Page 181
References......Page 182
Introduction......Page 183
Basics and Terminology......Page 185
$P_{3}$-Bicolorable Graphs......Page 187
P$_{4}$-Bicolorable Graphs......Page 189
P$_{4}$-Bicolorable Graphs and Related Graph Classes......Page 190
References......Page 192
Introduction......Page 194
Stability ($k$=1, tight)......Page 196
General (Loose)......Page 197
Cycle Covers......Page 198
Coflows and Integer Decomposition......Page 199
Coherence......Page 201
Topping......Page 202
Long Paths......Page 204
Corollaries for Path Partitions......Page 206
References......Page 209
Introduction......Page 211
Existence of PC Cycles......Page 212
P-Gadgets......Page 213
P-Gadget Graphs......Page 214
Long PC Cycles and Paths......Page 216
Longest PC Cycles and Paths in Edge-Coloured Complete Graphs......Page 217
References......Page 219
Preliminaries......Page 220
Representation of Antimatroidal Point Sets......Page 221
Recognition of Corner Points......Page 225
References......Page 227
Introduction......Page 228
Preliminaries......Page 230
The Robber and Captain Game......Page 231
Tree Projections and the C&R Game......Page 233
NP-Hardness......Page 234
References......Page 236
Author Index
......Page 238