Další formáty:
BibTeX
LaTeX
RIS
@article{637508,
author = {Hliněný, Petr},
article_location = {New York},
article_number = {1},
keywords = {matroid; spike; representability; minor},
language = {eng},
issn = {1432-4350},
journal = {Theory of Computing Systems},
title = {Some Hard Problems on Matroid Spikes},
url = {http://dx.doi.org/10.1007/s00224-007-1307-5},
volume = {41},
year = {2007}
}
TY - JOUR
ID - 637508
AU - Hliněný, Petr
PY - 2007
TI - Some Hard Problems on Matroid Spikes
JF - Theory of Computing Systems
VL - 41
IS - 1
SP - 551-562
EP - 551-562
PB - Springer
SN - 14324350
KW - matroid
KW - spike
KW - representability
KW - minor
UR - http://dx.doi.org/10.1007/s00224-007-1307-5
N2 - Spikes form an interesting class of $3$-connected matroids of branch-width~$3$. We show that some computational problems are hard on spikes with given matrix representations over infinite fields. Namely, the question whether a given spike is the free spike is co-$NP$-hard (though the property itself is definable in monadic second-order logic); and the task to compute the Tutte polynomial of a spike is $\#P$-hard (even though that can be solved efficiently on all matroids of bounded branch-width which are represented over a finite field).
ER -
HLINĚNÝ, Petr. Some Hard Problems on Matroid Spikes. \textit{Theory of Computing Systems}. New York: Springer, 2007, roč.~41, č.~1, s.~551-562. ISSN~1432-4350.
|
