EUDML

Currently displaying 1 – 9 of 9

Order by Relevance | Title | Year of publication

Nový pohled na algoritmickou matematiku

László Lovász — 1990

Pokroky matematiky, fyziky a astronomie

Je nový algoritmus lineárního programování lepší nebo horší než simplexová metoda?

László Lovász — 1981

Pokroky matematiky, fyziky a astronomie

On the null space of a Colin de Verdière matrix

Lászlo Lovász; Alexander Schrijver — 1999

Annales de l'institut Fourier

Let $G = (V, E)$ be a 3-connected planar graph, with $V = {1, ..., n}$ . Let $M = (m_{i, j})$ be a symmetric $n \times n$ matrix with exactly one negative eigenvalue (of multiplicity 1), such that for $i, j$ with $i \neq j$ , if $i$ and $j$ are adjacent then $m_{i, j} < 0$ and if $i$ and $j$ are nonadjacent then $m_{i, j} = 0$ , and such that $M$ has rank $n - 3$ . Then the null space $ker M$ of $M$ gives an embedding of $G$ in $S^{2}$ as follows: let ${a, b, c}$ be a basis of $ker M$ , and for $i \in V$ let $ϕ (i) : = (a_{i}, b_{i}, c_{i})^{T}$ ; then $ϕ (i) \neq 0$ , and $ψ (i) : = ϕ (i) / ∥ ϕ (i) ∥$ embeds $V$ in $S^{2}$ such that connecting, for any two adjacent vertices $i, j$ , the points $ψ (i)$ and $ψ (j)$ by a shortest geodesic on $S^{2}$ , gives...