Algorithms and Combinatorics

By: Kazuo Murota

Write A Review

Paperback | 18 November 2009 | Edition Number 2000

At a Glance

Paperback
496 Pages

Dimensions(cm)
23.5 x 15.5

Paperback

$219.00

or 4 interest-free payments of $54.75 with

Ships in 5 to 7 business days

A matroid is an abstract mathematical structure that captures combinatorial properties of matrices. This book offers a unique introduction to matroid theory, emphasizing motivations from matrix theory and applications to systems analysis.

This book serves also as a comprehensive presentation of the theory and application of mixed matrices, developed primarily by the present author in the 1990's. A mixed matrix is a convenient mathematical tool for systems analysis, compatible with the physical observation that "fixed constants" and "system parameters" are to be distinguished in the description of engineering systems.

This book will be extremely useful to graduate students and researchers in engineering, mathematics and computer science.

From the reviews:

"...The book has been prepared very carefully, contains a lot of interesting results and is highly recommended for graduate and postgraduate students."

Andr¡s Recski, Mathematical Reviews Clippings 2000m:93006

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

Orders over $89.00 qualify for free shipping.

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

Preface	p. v
Introduction to Structural Approach-Overview of the Book	p. 1
Structural Approach to Index of DAE	p. 1
Index of Differential-algebraic Equations	p. 1
Graph-theoretic Structural Approach	p. 3
An Embarrassing Phenomenon	p. 7
What Is Combinatorial Structure?	p. 10
Two Kinds of Numbers	p. 11
Descriptor Form Rather than Standard Form	p. 15
Dimensional Analysis	p. 17
Mathematics on Mixed Polynomial Matrices	p. 20
Formal Definitions	p. 20
Resolution of the Index Problem	p. 21
Block-triangular Decomposition	p. 26
Matrix, Graph, and Matroid	p. 31
Matrix	p. 31
Polynomial and Algebraic Independence	p. 31
Determinant	p. 33
Rank, Term-rank and Generic-rank	p. 36
Block-triangular Forms	p. 40
Graph	p. 43
Directed Graph and Bipartite Graph	p. 43
Jordan-Hölder-type Theorem for Submodular Functions	p. 48
Dulmage-Mendelsohn Decomposition	p. 55
Maximum Flow and Menger-type Linking	p. 65
Minimum Cost Flow and Weighted Matching	p. 67
Matroid	p. 71
From Matrix to Matroid	p. 71
Basic Concepts	p. 73
Examples	p. 77
Basis Exchange Properties	p. 78
Independent Matching Problem	p. 84
Union	p. 93
Bimatroid (Linking System)	p. 97
Physical Observations for Mixed Matrix Formulation	p. 107
Mixed Matrix for Modeling Two Kinds of Numbers	p. 107
Two Kinds of Numbers	p. 107
Mixed Matrix and Mixed Polynomial Matrix	p. 116
Algebraic Implication of Dimensional Consistency	p. 120
Introductory Comments	p. 120
Dimensioned Matrix	p. 121
Total Unimodularity of a Dimensioned Matrix	p. 123
Physical Matrix	p. 126
Physical Matrix	p. 126
Physical Matrices in a Dynamical System	p. 128
Theory and Application of Mixed Matrices	p. 131
Mixed Matrix and Layered Mixed Matrix	p. 131
Rank of Mixed Matrices	p. 134
Rank Identities for LM-matrices	p. 135
Rank Identities for Mixed Matrices	p. 139
Reduction to Independent Matching Problems	p. 142
Algorithms for the Rank	p. 145
Structural Solvability of Systems of Equations	p. 153
Formulation of Structural Solvability	p. 153
Graphical Conditions for Structural Solvability	p. 156
Matroidal Conditions for Structural Solvability	p. 160
Combinatorial Canonical Form of LM-matrices	p. 167
LM-equivalence	p. 167
Theorem of CCF	p. 172
Construction of CCF	p. 175
Algorithm for CCF	p. 181
Decomposition of Systems of Equations by CCF	p. 187
Application of CCF	p. 191
CCF over Rings	p. 199
Irreducibility of LM-matrices	p. 202
Theorems on LM-irreducibility	p. 202
Proof of the Irreducibility of Determinant	p. 205
Decomposition of Mixed Matrices	p. 211
LU-decomposition of Invertible Mixed Matrices	p. 212
Block-triangularization of General Mixed Matrices	p. 215
Related Decompositions	p. 221
Decomposition as Matroid Union	p. 221
Multilayered Matrix	p. 225
Electrical Network with Admittance Expression	p. 228
Partitioned Matrix	p. 230
Definitions	p. 231
Existence of Proper Block-triangularization	p. 235
Partial Order Among Blocks	p. 238
Generic Partitioned Matrix	p. 240
Principal Structures of LM-matrices	p. 250
Motivations	p. 250
Principal Structure of Submodular Systems	p. 252
Principal Structure of Generic Matrices	p. 254
Vertical Principal Structure of LM-matrices	p. 257
Horizontal Principal Structure of LM-matrices	p. 261
Polynomial Matrix and Valuated Matroid	p. 271
Polynomial/Rational Matrix	p. 271
Polynomial Matrix and Smith Form	p. 271
Rational Matrix and Smith-McMillan Form at Infinity	p. 272
Matrix Pencil and Kronecker Form	p. 275
Valuated Matroid	p. 280
Introduction	p. 280
Examples	p. 281
Basic Operations	p. 282
Greedy Algorithms	p. 285
Valuated Bimatroid	p. 287
Induction Through Bipartite Graphs	p. 290
Characterizations	p. 295
Further Exchange Properties	p. 300
Valuated Independent Assignment Problem	p. 306
Optimality Criteria	p. 308
Application to Triple Matrix Product	p. 316
Cycle-canceling Algorithms	p. 317
Augmenting Algorithms	p. 325
Theory and Application of Mixed Polynomial Matrices	p. 331
Descriptions of Dynamical Systems	p. 331
Mixed Polynomial Matrix Descriptions	p. 331
Relationship to Other Descriptions	p. 332
Degree of Determinant of Mixed Polynomial Matrices	p. 335
Introduction	p. 335
Graph-theoretic Method	p. 336
Basic Identities	p. 337
Reduction to Valuated Independent Assignment	p. 340
Duality Theorems	p. 343
Algorithm	p. 348
Smith Form of Mixed Polynomial Matrices	p. 355
Expression of Invariant Factors	p. 355
Proofs	p. 363
Controllability of Dynamical Systems	p. 364
Controllability	p. 364
Structural Controllability	p. 365
Mixed Polynomial Matrix Formulation	p. 372
Algorithm	p. 375
Examples	p. 379
Fixed Modes of Decentralized Systems	p. 384
Fixed Modes	p. 384
Structurally Fixed Modes	p. 387
Mixed Polynomial Matrix Formulation	p. 390
Algorithm	p. 395
Examples	p. 398
Further Topics	p. 403
Combinatorial Relaxation Algorithm	p. 403
Outline of the Algorithm	p. 403
Test for Upper-tightness	p. 407
Transformation Towards Upper-tightness	p. 413
Algorithm Description	p. 417
Combinatorial System Theory	p. 418
Definition of Combinatorial Dynamical Systems	p. 419
Power Products	p. 420
Eigensets and Recurrent Sets	p. 422
Controllability of Combinatorial Dynamical Systems	p. 426
Mixed Skew-symmetric Matrix	p. 431
Introduction	p. 431
Skew-symmetric Matrix	p. 433
Delta-matroid	p. 438
Rank of Mixed Skew-symmetric Matrices	p. 444
Electrical Network Containing Gyrators	p. 446
References	p. 453
Notation Table	p. 469
Index	p. 479
Table of Contents provided by Ingram. All Rights Reserved.

Algorithms and Combinatorics

At a Glance

Paperback

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Industrial Chemistry

How to Drink Natural Wine

Foundations of Flavor : The Noma Guide to Fermentation

Foundations of Flavor

Mary Penfold

The true story of the great Australian winemaker, from the bestselling award-winning author of SISTER VIV and MR AND MRS GOULD

Baked to Perfection

Winner of the Fortnum & Mason Food and Drink Awards 2022

The Farmhouse Culture Guide to Fermenting

Crafting Live-Cultured Foods and Drinks with 100 Recipes from Kimchi to Kombucha[A Cookbook]

The Hunger Code

how to reset your body's fat thermostat by breaking the ultra-processed-food habit

Fish Butchery

Mastering The Catch, Cut And Craft

The Ultimate Guide to Butchering, Smoking, Curing, Sausage, and Jerky Making

How To Brew

Everything You Need to Know to Brew Great Beer Every Time

Flame Retardant Materials

Manufacturing, Applications, and Environmental Perspectives

Plastic Inc

Big Oil, Big Money and The Plan To Trash Our Future

The Truth about Seed Oils

How the Heart-Healthy Myth Made Us Sick--And How to Heal with Real Fats

Preserving Food without Freezing or Canning

Traditional Techniques Using Salt, Oil, Sugar, Alcohol, Vinegar, Drying, Cold Storage, and Lactic Fermentation

The World Atlas of Wine : 8th Edition

Professional Beauty Therapy

4th Edition - Australia and New Zealand

The Science of Spice

Understand Flavour Connections and Revolutionize your Cooking

Food Engineering

Techniques and Technology

Food Antioxidants

Toxicological and Health Perspectives

Viticulture and Winemaking

The Role of Microorganisms

Foodborne Bacterial Pathogens

Food Microbiology and Food Safety

Advances in Food Microbiology

Fermented Foods and Alcoholic Beverages

Home Cheese Making : 4th Edition

From Fresh and Soft to Firm, Blue, Goat's Milk and More; Recipes for 100 Favorite Cheeses

French Pâtisserie

Master Recipes and Techniques from the Ferrandi School of Culinary Arts

Wild Clay

Creating Ceramics and Glazes from Natural and Found Resources

This product is categorised by