About: On matroid representability and minor problems

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: On matroid representability and minor problems Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
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. 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. (en) 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. (cs)
Title	On matroid representability and minor problems On matroid representability and minor problems (en) On matroid representability and minor problems (cs)
skos:prefLabel	On matroid representability and minor problems On matroid representability and minor problems (en) On matroid representability and minor problems (cs)
skos:notation	RIV/61989100:27240/06:00013584!RIV08-AV0-27240___
http://linked.open.../vavai/riv/strany	505-516
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(1ET101940420), P(1M0545), P(GA201/05/0050)
http://linked.open...iv/cisloPeriodika	4126
http://linked.open...vai/riv/dodaniDat	2008
http://linked.open...aciTvurceVysledku	Hliněný, Petr
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Vysoká škola báňská - Technická univerzita Ostrava / Fakulta elektrotechniky a informatiky
http://linked.open...dnocenehoVysledku	490354
http://linked.open...ai/riv/idVysledku	RIV/61989100:27240/06:00013584
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	matroid; spike; representability; minor; NP-completeness (en)
http://linked.open.../riv/klicoveSlovo	minor NP-completeness spike matroid representability
http://linked.open...odStatuVydavatele	DE - Spolková republika Německo
http://linked.open...ontrolniKodProRIV	[460E7006963B]
http://linked.open...i/riv/nazevZdroje	MFCS 2006
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	1 (xsd:int)
http://linked.open...vavai/riv/projekt	Logic and Artificial Intelligence in the area of Multiagent Systems Institute for Theoretical Computer Science Structural properties and algorithmic complexity of discrete problems
http://linked.open...UplatneniVysledku	2006
http://linked.open...v/svazekPeriodika	2006
http://linked.open...iv/tvurceVysledku	Hliněný, Petr
issn	0302-9743
number of pages	12 (xsd:int)
http://localhost/t...ganizacniJednotka	27240
is http://linked.open...avai/riv/vysledek of	On matroid representability and minor problems On matroid representability and minor problems

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software