On Matroid Representability and Minor Problems
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F06%3A00015807" target="_blank" >RIV/00216224:14330/06:00015807 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
On Matroid Representability and Minor Problems
Original language description
In this paper we look at complexity aspects of the following problem (matroid representability) which seems to play an important role in structural matroid theory: Given a rational matrix representing the matroid $M$, the question is whether $M$ can be represented also over another specific finite field. We prove this problem is hard, and so is the related problem of minor testing in rational matroids. The results hold even if we restrict to matroids of branch-width three.
Czech name
O problémech reprezentovatelnosti a minorů na matroidech
Czech description
Článek dokazuje těžkost problémů reprezentovatelnosi matroidů a testování matroidových minorů.
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
31st International Symposium, MFCS 2006
ISBN
3-540-37791-3
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
—
Publisher name
Springer Verlag
Place of publication
Berlin
Event location
Stará Lesná, Slovakia
Event date
Aug 28, 2006
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000240271700044