Matching minors in bipartite graphs
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...
Saved in:
Superior document: | Foundations of computing |
---|---|
: | |
Year of Publication: | 2022 |
Language: | English |
Series: | Foundations of computing
|
Physical Description: | 1 electronic resource (476 p.) |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
id |
993549278004498 |
---|---|
ctrlnum |
(CKB)5700000000101233 (oapen)https://directory.doabooks.org/handle/20.500.12854/87653 (EXLCZ)995700000000101233 |
collection |
bib_alma |
record_format |
marc |
spelling |
Wiederrecht, Sebastian auth Matching minors in bipartite graphs Berlin Universitätsverlag der Technischen Universität Berlin 2022 1 electronic resource (476 p.) text txt rdacontent computer c rdamedia online resource cr rdacarrier Foundations of computing 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. English Algorithms & data structures bicssc matching minor; structural graph theory; bipartite; perfect matching 3-7983-3252-5 |
language |
English |
format |
eBook |
author |
Wiederrecht, Sebastian |
spellingShingle |
Wiederrecht, Sebastian Matching minors in bipartite graphs Foundations of computing |
author_facet |
Wiederrecht, Sebastian |
author_variant |
s w sw |
author_sort |
Wiederrecht, Sebastian |
title |
Matching minors in bipartite graphs |
title_full |
Matching minors in bipartite graphs |
title_fullStr |
Matching minors in bipartite graphs |
title_full_unstemmed |
Matching minors in bipartite graphs |
title_auth |
Matching minors in bipartite graphs |
title_new |
Matching minors in bipartite graphs |
title_sort |
matching minors in bipartite graphs |
series |
Foundations of computing |
series2 |
Foundations of computing |
publisher |
Universitätsverlag der Technischen Universität Berlin |
publishDate |
2022 |
physical |
1 electronic resource (476 p.) |
isbn |
3-7983-3252-5 |
illustrated |
Not Illustrated |
work_keys_str_mv |
AT wiederrechtsebastian matchingminorsinbipartitegraphs |
status_str |
n |
ids_txt_mv |
(CKB)5700000000101233 (oapen)https://directory.doabooks.org/handle/20.500.12854/87653 (EXLCZ)995700000000101233 |
carrierType_str_mv |
cr |
hierarchy_parent_title |
Foundations of computing |
is_hierarchy_title |
Matching minors in bipartite graphs |
container_title |
Foundations of computing |
_version_ |
1796651924413480960 |
fullrecord |
<?xml version="1.0" encoding="UTF-8"?><collection xmlns="http://www.loc.gov/MARC21/slim"><record><leader>01868nam-a2200289z--4500</leader><controlfield tag="001">993549278004498</controlfield><controlfield tag="005">20231214133046.0</controlfield><controlfield tag="006">m o d </controlfield><controlfield tag="007">cr|mn|---annan</controlfield><controlfield tag="008">202207s2022 xx |||||o ||| 0|eng d</controlfield><datafield tag="035" ind1=" " ind2=" "><subfield code="a">(CKB)5700000000101233</subfield></datafield><datafield tag="035" ind1=" " ind2=" "><subfield code="a">(oapen)https://directory.doabooks.org/handle/20.500.12854/87653</subfield></datafield><datafield tag="035" ind1=" " ind2=" "><subfield code="a">(EXLCZ)995700000000101233</subfield></datafield><datafield tag="041" ind1="0" ind2=" "><subfield code="a">eng</subfield></datafield><datafield tag="100" ind1="1" ind2=" "><subfield code="a">Wiederrecht, Sebastian</subfield><subfield code="4">auth</subfield></datafield><datafield tag="245" ind1="1" ind2="0"><subfield code="a">Matching minors in bipartite graphs</subfield></datafield><datafield tag="260" ind1=" " ind2=" "><subfield code="a">Berlin</subfield><subfield code="b">Universitätsverlag der Technischen Universität Berlin</subfield><subfield code="c">2022</subfield></datafield><datafield tag="300" ind1=" " ind2=" "><subfield code="a">1 electronic resource (476 p.)</subfield></datafield><datafield tag="336" ind1=" " ind2=" "><subfield code="a">text</subfield><subfield code="b">txt</subfield><subfield code="2">rdacontent</subfield></datafield><datafield tag="337" ind1=" " ind2=" "><subfield code="a">computer</subfield><subfield code="b">c</subfield><subfield code="2">rdamedia</subfield></datafield><datafield tag="338" ind1=" " ind2=" "><subfield code="a">online resource</subfield><subfield code="b">cr</subfield><subfield code="2">rdacarrier</subfield></datafield><datafield tag="490" ind1="1" ind2=" "><subfield code="a">Foundations of computing</subfield></datafield><datafield tag="520" ind1=" " ind2=" "><subfield code="a">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.</subfield></datafield><datafield tag="546" ind1=" " ind2=" "><subfield code="a">English</subfield></datafield><datafield tag="650" ind1=" " ind2="7"><subfield code="a">Algorithms & data structures</subfield><subfield code="2">bicssc</subfield></datafield><datafield tag="653" ind1=" " ind2=" "><subfield code="a">matching minor; structural graph theory; bipartite; perfect matching</subfield></datafield><datafield tag="776" ind1=" " ind2=" "><subfield code="z">3-7983-3252-5</subfield></datafield><datafield tag="906" ind1=" " ind2=" "><subfield code="a">BOOK</subfield></datafield><datafield tag="ADM" ind1=" " ind2=" "><subfield code="b">2023-12-15 05:41:16 Europe/Vienna</subfield><subfield code="f">system</subfield><subfield code="c">marc21</subfield><subfield code="a">2022-07-14 08:50:39 Europe/Vienna</subfield><subfield code="g">false</subfield></datafield><datafield tag="AVE" ind1=" " ind2=" "><subfield code="i">DOAB Directory of Open Access Books</subfield><subfield code="P">DOAB Directory of Open Access Books</subfield><subfield code="x">https://eu02.alma.exlibrisgroup.com/view/uresolver/43ACC_OEAW/openurl?u.ignore_date_coverage=true&portfolio_pid=5338973110004498&Force_direct=true</subfield><subfield code="Z">5338973110004498</subfield><subfield code="b">Available</subfield><subfield code="8">5338973110004498</subfield></datafield></record></collection> |