On Matroid Representability and Minor Problems

HLINĚNÝ, Petr. On Matroid Representability and Minor Problems. In 31st International Symposium, MFCS 2006. 4162. vyd. Berlin: Springer Verlag, 2006, s. 505-516. ISBN 3-540-37791-3.

Základní údaje

Originální název

On Matroid Representability and Minor Problems

Název česky

O problémech reprezentovatelnosti a minorů na matroidech

Autoři

HLINĚNÝ, Petr (203 Česká republika, garant)

Vydání

4162. vyd. Berlin, 31st International Symposium, MFCS 2006, od s. 505-516, 12 s. 2006

Nakladatel

Springer Verlag

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Kód RIV

RIV/00216224:14330/06:00015807

Organizační jednotka

Fakulta informatiky

ISBN

3-540-37791-3

UT WoS

000240271700044

Klíčová slova anglicky

crossing number; crossing minimization; planarization; crossing-critical graphs

Štítky

crossing minimization, crossing number, crossing-critical graphs, planarization

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

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.

Česky

Článek dokazuje těžkost problémů reprezentovatelnosi matroidů a testování matroidových minorů.

---

Návaznosti

GA201/05/0050, projekt VaV	Název: Strukturální vlastnosti a algoritmická složitost diskrétních problémů
1M0545, projekt VaV	Název: Institut Teoretické Informatiky Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky