Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{693907,
author = {Hliněný, Petr},
address = {Berlin},
booktitle = {31st International Symposium, MFCS 2006},
edition = {4162},
keywords = {crossing number; crossing minimization; planarization; crossing-critical graphs},
language = {eng},
location = {Berlin},
isbn = {3-540-37791-3},
pages = {505-516},
publisher = {Springer Verlag},
title = {On Matroid Representability and Minor Problems},
url = {http://www.mfcs.sk/mfcs2006/},
year = {2006}
}
TY - JOUR
ID - 693907
AU - Hliněný, Petr
PY - 2006
TI - On Matroid Representability and Minor Problems
PB - Springer Verlag
CY - Berlin
SN - 3540377913
KW - crossing number
KW - crossing minimization
KW - planarization
KW - crossing-critical graphs
UR - http://www.mfcs.sk/mfcs2006/
N2 - 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.
ER -
HLINĚNÝ, Petr. On Matroid Representability and Minor Problems. In \textit{31st International Symposium, MFCS 2006}. 4162. vyd. Berlin: Springer Verlag. s.~505-516. ISBN~3-540-37791-3. 2006.
|
