An algorithm for constructing star-shaped drawings of plane graphs

A straight-line planar drawing of a plane graph is called a convex drawing if every facial cycle is drawn as a convex polygon. Convex drawings of graphs is a well-established aesthetic in graph drawing, however not all planar graphs admit a convex drawing. Tutte [W.T. Tutte, Convex representations of graphs, Proc. of London Math. Soc. 10 (3) (1960) 304–320] showed that every triconnected plane graph admits a convex drawing for any given boundary drawn as a convex polygon. Thomassen [C. Thomassen, Plane representations of graphs, in: Progress in Graph Theory, Academic Press, 1984, pp. 43–69] gave a necessary and sufficient condition for a biconnected plane graph with a prescribed convex boundary to have a convex drawing.In this paper, we initiate a new notion of star-shaped drawing of a plane graph as a straight-line planar drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. A star-shaped drawing is a natural extension of a convex drawing, and a new aesthetic criteria for drawing planar graphs in a convex way as much as possible. We give a sufficient condition for a given set A of corners of a plane graph to admit a star-shaped drawing whose concave corners are given by the corners in A, and present a linear time algorithm for constructing such a star-shaped drawing.     

Box-Rectangular Drawings of Plane Graphs

In this paper we introduce a new drawing style of a plane graph G called a box-rectangular drawing. It is defined to be a drawing of G on an integer grid such that every vertex is drawn as a rectangle, called a box, each edge is drawn as either a horizontal line segment or a vertical line segment, and the contour of each face is drawn as a rectangle. We establish a necessary and sufficient condition for the existence of a box-rectangular drawing of G. We also give a linear-time algorithm to find a box-rectangular drawing of G if it exists.     

On farthest points of sets

For a convex closed bounded set in a Banach space, we study the existence and uniqueness problem for a point of this set that is the farthest point from a given point in space. In terms of the existence and uniqueness of the farthest point, as well as the Lipschitzian dependence of this point on a point in space, we obtain necessary and su.cient conditions for the strong convexity of a set in several infinite-dimensional spaces, in particular, in a Hilbert space. A set representable as the intersection of closed balls of a fixed radius is called a strongly convex set. We show that the condition “for each point in space that is sufficiently far from a set, there exists a unique farthest point of the set” is a criterion for the strong convexity of a set in a finite-dimensional normed space, where the norm ball is a strongly convex set and a generating set.     

The KdV soliton crosses a dissipative and dispersive border

We demonstrate the behavior of the soliton which, while moving in non-dissipative and dispersion-constant medium encounters a finite-width barrier with varying dissipation and/or dispersion; beyond the layer dispersion is constant (but not necessarily of the same value) and dissipation is null. The transmitted wave either retains the form of a soliton (though of different parameters) or scatters a into a number of them. And a reflection wave may be negligible or absent. This models a situation similar to a light passing from a humid air to a dry one through the vapor saturation/condensation area. Some rough estimations for a prediction of an output are given using the relative decay (or accumulation) of the KdV conserved quantities in a dissipative area; in particular for a restriction for a number of solitons in the transmitted signal.     

Scalarization of Henig Proper Efficient Points in a Normed Space

In a general normed space equipped with the order induced by a closed convex cone with a base, using a family of continuous monotone Minkowski functionals and a family of continuous norms, we obtain scalar characterizations of Henig proper efficient points of a general set and a bounded set, respectively. Moreover, we give a scalar characterization of a superefficient point of a set in a normed space equipped with the order induced by a closed convex cone with a bounded base.     

Staircase Parameterization in Dynamical Selection

This paper deals with a variant of a dynamical selection scheme introduced by Attouch and Cominetti for ill-posed convex minimization which combines approximation with the steepest descent method by mean of a suitable parameterization of the approximation parameter as a function of the time. This variant applies to a general inclusion with a maximal monotone operator by mean of a staircase parameterization. A discrete analogue is also considered. Applications to selecting a particular zero of a maximal monotone operator or a particular fixed point of a nonexpansive mapping via regularization techniques are presented. Finally, the alternative use of well-posedness by perturbations is discussed.     

Enumerating bases of self-dual matroids

We define involutively self-dual matroids and prove that an enumerator for their bases is the square of a related enumerator for their self-dual bases. This leads to a new proof of Tutte's theorem that the number of spanning trees of a central reflex is a perfect square, and it solves a problem posed by Kalai about higher dimensional spanning trees in simplicial complexes. We also give a weighted version of the latter result.We give an algebraic analogue relating to the critical group of a graph, a finite abelian group whose order is the number of spanning trees of the graph. We prove that the critical group of a central reflex is a direct sum of two copies of an abelian group, and conclude with an analogous result in Kalai's setting.     

管状曲面在曲线论中的应用

研究了围绕曲线的管状曲面上的曲率线,渐近线与测地线,给出它们的方程,揭示了这些曲线与Bertrand曲线或Mannheim曲线之间的关系,采用新的方法给出一条曲线是Bertrand曲线或Mannheim曲线的充要条件的另一种证明以及Mannheim侣线的曲率与挠率之间的关系．     

Mean-variance portfolio selection for a non-life insurance company

We consider a collective insurance risk model with a compound Cox claim process, in which the evolution of a claim intensity is described by a stochastic differential equation driven by a Brownian motion. The insurer operates in a financial market consisting of a risk-free asset with a constant force of interest and a risky asset which price is driven by a Lévy noise. We investigate two optimization problems. The first one is the classical mean-variance portfolio selection. In this case the efficient frontier is derived. The second optimization problem, except the mean-variance terminal objective, includes also a running cost penalizing deviations of the insurer’s wealth from a specified profit-solvency target which is a random process. In order to find optimal strategies we apply techniques from the stochastic control theory.     

Weak Convergence Theorems for Nonexpansive Mappings and Monotone Mappings

In this paper, we introduce an iteration process of finding a common element of the set of fixed points of a nonexpansive mapping and the set of solutions of a variational inequality problem for an inverse strongly-monotone mapping, and then obtain a weak convergence theorem. Using this result, we obtain a weak convergence theorem for a pair of a nonexpansive mapping and a strictly pseudocontractive mapping. Further, we consider the problem of finding a common element of the set of fixed points of a nonexpansive mapping and the set of zeros of an inverse strongly-monotone mapping.     

On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width

Rank-width is a structural graph measure introduced by Oum and Seymour and aimed at better handling of graphs of bounded clique-width. We propose a formal mathematical framework and tools for easy design of dynamic algorithms running directly on a rank-decomposition of a graph (on contrary to the usual approach which translates a rank-decomposition into a clique-width expression, with a possible exponential jump in the parameter). The main advantage of this framework is a fine control over the runtime dependency on the rank-width parameter. Our new approach is linked to a work of Courcelle and Kanté [7] who first proposed algebraic expressions with a so-called bilinear graph product as a better way of handling rank-decompositions, and to a parallel recent research of Bui-Xuan, Telle and Vatshelle.     

Filters in (Quasiordered) Semigroups and Lattices of Filters

A filter in a semigroup is a subsemigroup whose complement is an ideal. (Alternatively, in a quasiordered semigroup, a slightly more general definition can be given.) We prove a number of results related to filters in a semigroup and the lattice of filters of a semigroup. For instance, we prove that every complete algebraic lattice can be the lattice of filters of a semigroup. We prove that every finite semigroup is a homomorphic image of a finite semigroup whose lattice of filters is boolean and which belongs to the pseudovariety generated by the original semigroup. We describe filter lattices of some well-known semigroups such as full transformation semigroups of finite sets (which are three-element chains) and free semigroups (which are boolean).     

Fundamental groups,inverse schützenberger automata,and monoid presentations

This paper gives decidable conditions for when a finitely generated subgroup of a free group is the fundamental group of a Schützenberger automaton corresponding to a monoid presentation of an inverse monoid. Also, generalizations are given to specific types of inverse monoids as well as to monoids which are "nearly inverse." This result has applications to computing membership for inverse monoids in a Mal'cev product of the pseudovariety of semilattices with a pseudovariety of groups.

This paper also shows that there is a bijection between strongly connected inverse automata and subgroups of a free group, generated by positive words. Hence, we also obtain that it is decidable whether a finite strongly connected inverse automaton is a Schützenberger automaton corresponding to a monoid presentation of an inverse monoid. Again, we have generalizations to other types of inverse monoids and to "nearly inverse" monoids. We show that it is undecidable whether a finite strongly connected inverse automaton is a Schützenberger automaton of a monoid presentation of anE-unitary inverse monoid.     

Certificates of Primal or Dual Infeasibility in Linear Programming

In general if a linear program has an optimal solution, then a primal and dual optimal solution is a certificate of the solvable status. Furthermore, it is well known that in the solvable case, then the linear program always has an optimal basic solution. Similarly, when a linear program is primal or dual infeasible then by Farkas's Lemma a certificate of the infeasible status exists. However, in the primal or dual infeasible case then there is not an uniform definition of what a suitable basis certificate of the infeasible status is.In this work we present a definition of a basis certificate and develop a strongly polynomial algorithm which given a Farkas type certificate of infeasibility computes a basis certificate of infeasibility. This result is relevant for the recently developed interior-point methods because they do not compute a basis certificate of infeasibility in general. However, our result demonstrates that a basis certificate can be obtained at a moderate computational cost.     

New parameters of subsets in polynomial association schemes

We define new parameters, a zero interval and a dual zero interval, of subsets in P- or Q-polynomial association schemes. A zero interval of a subset in a P-polynomial association scheme is a successive interval index for which the inner distribution vanishes, and a dual zero interval of a subset in a Q-polynomial association scheme is a successive interval index for which the dual inner distribution vanishes. We derive bounds of the lengths of a zero interval and a dual zero interval using the degree and dual degree respectively, and show that a subset in a P-polynomial association scheme (resp. a Q-polynomial association scheme) having a large length of a zero interval (resp. a dual zero interval) induces a completely regular code (resp. a Q-polynomial association scheme). Moreover, we consider the spherical analogue of a dual zero interval.     

Palm calculus for a process with a stationary random measure and its applications to fluid queues

We consider a process associated with a stationary random measure, which may have infinitely many jumps in a finite interval. Such a process is a generalization of a process with a stationary embedded point process, and is applicable to fluid queues. Here, fluid queue means that customers are modeled as a continuous flow. Such models naturally arise in the study of high speed digital communication networks. We first derive the rate conservation law (RCL) for them, and then introduce a process indexed by the level of the accumulated input. This indexed process can be viewed as a continuous version of a customer characteristic of an ordinary queue, e.g., of the sojourn time. It is shown that the indexed process is stationary under a certain kind of Palm probability measure, called detailed Palm. By using this result, we consider the sojourn time processes in fluid queues. We derive the continuous version of Little's formula in our framework. We give a distributional relationship between the buffer content and the sojourn time in a fluid queue with a constant release rate.     

On arithmetic Macaulayfication of Noetherian rings

The Rees algebra is the homogeneous coordinate ring of a blowing-up. The present paper gives a necessary and sufficient condition for a Noetherian local ring to have a Cohen-Macaulay Rees algebra: A Noetherian local ring has a Cohen-Macaulay Rees algebra if and only if it is unmixed and all the formal fibers of it are Cohen-Macaulay. As a consequence of it, we characterize a homomorphic image of a Cohen-Macaulay local ring. For non-local rings, this paper gives only a sufficient condition. By using it, however, we obtain the affirmative answer to Sharp's conjecture. That is, a Noetherian ring having a dualizing complex is a homomorphic image of a finite-dimensional Gorenstein ring.

     

A pair of orthogonal frames

We start with a characterization of a pair of frames to be orthogonal in a shift-invariant space and then give a simple construction of a pair of orthogonal shift-invariant frames. This is applied to obtain a construction of a pair of Gabor orthogonal frames as an example. This is also developed further to obtain constructions of a pair of orthogonal wavelet frames.     

非扩张映射的不动点与变分包含问题的公共解

In this paper, we introduce an iterative scheme for finding a common element of the set of fixed points of a nonexpansive mapping and the set of solutions of the variational inclusion for an inverse-strongly monotone mapping and a maximal monotone mapping in a real Hilbert space. Then we show that the sequence converges strongly to a common element of two sets. Using the result, we consider the problem of finding a common fixed point of a nonexpansive mapping and a strictly pseudocontractive mapping in a real Hilbert space.