Opuscula Mathematica
Loading...
ISSN 1232-9274
e-ISSN: 2300-6919
Issue Date
2008
Volume
Vol. 28
Number
No. 3
Description
Journal Volume
Opuscula Mathematica
Vol. 28 (2008)
Projects
Pages
Articles
3-biplacement of bipartite graphs
(2008) Adamus, Lech; Leśniak, Edyta; Orchel, Beata
Let $G=(L,R;E)$ be a bipartite graph with color classes $L$ and $R$ and edge set $E$. A set of two bijections $\{\varphi_1 , \varphi_2\}$, $\varphi_1 , \varphi_2 :L \cup R \to L \cup R$, is said to be a $3$-biplacement of $G$ if $\varphi_1(L)= \varphi_2(L) = L$ and $E \cap \varphi_1^*(E)=\emptyset$, $E \cap \varphi_2^*(E)=\emptyset$, $\varphi_1^*(E) \cap \varphi_2^*(E)=\emptyset$, where$\varphi_1^*$, $\varphi_2^*$ are the maps defined on $E$, induced by $\varphi_1$, $\varphi_2$, respectively. We prove that if $|L|=p$, $|R|=q$, $3 \leq p \leq q$, then every graph $G=(L,R;E)$ of size at most $p$ has a $3$-biplacement.
Functional models for Nevanlinna families
(2008) Behrndt, Jussi; Hassi, Seppo; Snoo, Henk de
The class of Nevanlinna families consists of $\mathbb{R}$-symmetric holomorphic multivalued functions on $\mathbb{C} \setminus \mathbb{R}$ with maximal dissipative (maximal accumulative) values on $\mathbb{C}_{+}$ ($\mathbb{C}_{-}$, respectively) and is a generalization of the class of operator-valued Nevanlinna functions. In this note Nevanlinna families are realized as Weyl families of boundary relations induced by multiplication operators with the independent variable in reproducing kernel Hilbert spaces.
Randomized and quantum algorithms for solving initial-value problems in ordinary differential equations of order k
(2008) Goćwin, Maciej; Szczęsny, Marek
The complexity of initial-value problems is well studied for systems of equations of first order. In this paper, we study the $\varepsilon$-complexity for initial-value problems for scalar equations of higher order. We consider two models of computation, the randomized model and the quantum model. We construct almost optimal algorithms adjusted to scalar equations of higher order, without passing to systems of first order equations. The analysis of these algorithms allows us to establish upper complexity bounds. We also show (almost) matching lower complexity bounds. The $\varepsilon$-complexity in the randomized and quantum setting depends on the regularity of the right-hand side function, but is independent of the order of equation. Comparing the obtained bounds with results known in the deterministic case, we see that randomized algorithms give us a speed-up by $1/2$, and quantum algorithms by $1$ in the exponent. Hence, the speed-up does not depend on the order of equation, and is the same as for the systems of equations of first order. We also include results of some numerical experiments which confirm theoretical results.
Strong geodomination in graphs
(2008) Rad, Nader Jafari; Mojdeh, Doost Ali
A pair $x$, $y$ of vertices in a nontrivial connected graph $G$ is said to geodominate a vertex $v$ of $G$ if either $v \in \{x, y\}$ or $v$ lies in an $x - y$ geodesic of $G$. A set $S$ of vertices of $G$ is a geodominating set if every vertex of $G$ is geodominated by some pair of vertices of $S$. In this paper we study strong geodomination in a graph $G$.
Generalized characteristic singular integral equation with Hilbert kernel
(2008) Karczmarek, Paweł
In this paper an explicit solution of a generalized singular integral equation with a Hilbert kernel depending on indices of characteristic operators is presented.