Explore
Matching minors in bipartite graphs
0 Ungluers have
Faved this Work
Login to Fave
In this thesis we adapt fundamental parts of the Graph Minors series of Robertson and Seymour for the study of matching minors and investigate a connection to the study of directed graphs. We develope matching theoretic to established results of graph minor theory: We characterise the existence of a cross over a conformal cycle by means of a topological property. Furthermore, we develope a theory for perfect matching width, a width parameter for graphs with perfect matchings introduced by Norin. here we show that the disjoint alternating paths problem can be solved in polynomial time on graphs of bounded width. Moreover, we show that every bipartite graph with high perfect matching width must contain a large grid as a matching minor. Finally, we prove an analogue of the we known Flat Wall theorem and provide a qualitative description of all bipartite graphs which exclude a fixed matching minor.
This book is included in DOAB.
Why read this book? Have your say.
You must be logged in to comment.
Rights Information
Are you the author or publisher of this work? If so, you can claim it as yours by registering as an Unglue.it rights holder.Downloads
This work has been downloaded 32 times via unglue.it ebook links.
- 32 - pdf (CC BY) at OAPEN Library.
Keywords
- Algorithms & data structures
- bipartite
- Computer programming / software development
- Computing & information technology
- matching minor
- perfect matching
- structural graph theory
- thema EDItEUR::U Computing and Information Technology::UM Computer programming / software engineering::UMB Algorithms and data structures
Links
DOI: 10.14279/depositonce-14958Editions