Bridging Separations in Matroids

HLINĚNÝ, Petr, Jim GEELEN a Geoff WHITTLE. Bridging Separations in Matroids. SIAM Journal on Discrete Mathematics. Philadelphia: SIAM, roč. 18, č. 3, s. 638-646. ISSN 0895-4801. 2005.

Základní údaje

• Originální název: Bridging Separations in Matroids
• Název česky: Přemostění separací v matroidech
• Autoři: HLINĚNÝ, Petr (203 Česká republika, garant), Jim GEELEN (36 Austrálie) a Geoff WHITTLE (36 Austrálie).
• Vydání: SIAM Journal on Discrete Mathematics, Philadelphia, SIAM, 2005, 0895-4801.

Další údaje

• Originální jazyk: angličtina
• Typ výsledku: Článek v odborném periodiku
• Obor: 10101 Pure mathematics
• Stát vydavatele: Spojené státy
• Utajení: není předmětem státního či obchodního tajemství
• Impakt faktor: Impact factor: 0.885
• Kód RIV: RIV/00216224:14330/05:00028918
• Organizační jednotka: Fakulta informatiky
• UT WoS: 000228918000018
• Klíčová slova anglicky: matroid; separation
• Štítky: matroids
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

Let $(X_1,X_2)$ be an exact $k$--separation of a matroid $N$. If $M$ is a matroid that contains $N$ as a minor and the $k$--separation $(X_1,X_2)$ does not extend to a $k$--separation in $M$ then we say that $M$ {\em bridges} the $k$--separation $(X_1,X_2)$ in $N$. One would hope that a minor minimal bridge for $(X_1,X_2)$ would not be much larger than $N$. Unfortunately there are instances in which one can construct arbitaraily large minor minimal bridges. We restrict our attention to the class of matroids representable over a fixed finite field and show that here minor minimal bridges are bounded in size.

Anotace česky

Dokazujeme, že minorově minimální přemostění dané separace v konečně reprezentovaném matroidu je vždy omezeně velké.

Návaznosti

• GA201/05/0050, projekt VaV: Název: Strukturální vlastnosti a algoritmická složitost diskrétních problémů