Home > Search Results: keywords:"FOL properties"
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 1 records found  Search took 0.01 seconds. 
Algorithmic metatheorems for matroids
 Toufar, Tomáš ; Pangrác, Ondřej (advisor) ; Dvořák, Zdeněk (referee)
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.
Detailed record

Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English