Original title:
Algoritmické metavěty pro matroidy
Translated title:
Algorithmic metatheorems for matroids
Authors:
Toufar, Tomáš ; Pangrác, Ondřej (advisor) ; Dvořák, Zdeněk (referee) Document type: Bachelor's theses
Year:
2015
Language:
eng Abstract:
[eng][cze] In the thesis we define a new width parameter for matroids called amal- gam width that is based on the operation of matroid amalgamation. The parameter is related to branch width for matroids representable over fixed fi- nite field in the sense that class of representable matroids of bounded branch width has bounded amalgam width. The decomposition allows us to decide monadic second-order properties in linear time on matroids of bounded amal- gam width, even for matroids that are not representable (provided we are given the decomposition). We also prove that the coefficients of the Tutte polynomial can be computed in polynomial time for matroids of bounded amalgam width.V práci definujeme nový šířkový parametr pro matroidy nazvaný amal- gamační šířka. Tento šířkový parametr vychází z operace amalgamace ma- troidů. Parametr má úzký vztah k větvící šířce (branch width) na matroidech reprezentovatelných nad pevně zvoleným konečným tělesem - reprezento- vatelné matroidy s omezenou větvící šířkou mají omezenou i amalgamační šířku. Přitom jsme stále schopni rozhodovat vlastnosti v monadické log- ice druhého řádu v lineárním čase pro matroidy s omezenou amalgamační šířkou a to i tehdy, když matroid není reprezentovatelný (pokud ovšem máme dekompozici danou). Navíc dokážeme spočíst koeficienty Tutteho polynomu matroidu v polynomiálním čase na třídách matroidů s omezenou amalgamační šířkou.
Keywords:
algorithms; FOL properties; matroids; MSOL properties; width parameters; algoritmy; FOL vlastnosti; matroidy; MSOL vlastnosti; šířkové parametry
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/63626