Drawing slicing graphs with face areas

We consider orthogonal drawings of a plane graph G$G$ with specified face areas. For a natural number k$k$, a k$k$-gonal drawing of G$G$ is an orthogonal drawing such that the boundary of G$G$ is drawn as a rectangle and each inner face is drawn as a polygon with at most k$k$ corners whose area is equal to the specified value. In this paper, we show that every slicing graph G$G$ with a slicing tree T$T$ and a set of specified face areas admits a 10-gonal drawing D$D$ such that the boundary of each slicing subgraph that appears in T$T$ is also drawn as a polygon with at most 10 corners. Such a drawing D$D$ can be found in linear time.     

Approximating the Maximum Internal Spanning Tree problem

Given an undirected connected graph G$G$ we consider the problem of finding a spanning tree of G$G$ which has a maximum number of internal (non-leaf) vertices among all spanning trees of G$G$. This problem, called Maximum Internal Spanning Tree problem, is clearly NP-hard since it is a generalization of the Hamiltonian Path problem. From the optimization point of view the Maximum Internal Spanning Tree problem is equivalent to the Minimum Leaf Spanning Tree problem. However, the two problems have different approximability properties. Lu and Ravi proved that the latter has no constant factor approximation–unless P = NP–, while Salamon and Wiener gave a linear-time 2-approximation algorithm for the Maximum Internal Spanning Tree problem.     

On semimeasures predicting Martin-Löf random sequences

Solomonoff’s central result on induction is that the prediction of a universal semimeasure M$M$ converges rapidly and with probability 1 to the true sequence generating predictor μ$\mu$, if the latter is computable. Hence, M$M$ is eligible as a universal sequence predictor in the case of unknown μ$\mu$. Despite some nearby results and proofs in the literature, the stronger result of convergence for all (Martin-Löf) random sequences remained open. Such a convergence result would be particularly interesting and natural, since randomness can be defined in terms of M$M$ itself. We show that there are universal semimeasures M$M$ which do not converge to μ$\mu$ on all μ$\mu$-random sequences, i.e. we give a partial negative answer to the open problem. We also provide a positive answer for some non-universal semimeasures. We define the incomputable measure D$D$ as a mixture over all computable measures and the enumerable semimeasure W$W$ as a mixture over all enumerable nearly measures. We show that W$W$ converges to D$D$ and D$D$ to μ$\mu$ on all random sequences. The Hellinger distance measuring closeness of two distributions plays a central role.     

Local edge colouring of Yao-like subgraphs of Unit Disk Graphs

The focus of the present paper is on providing a local deterministic algorithm for colouring the edges of Yao-like   subgraphs of Unit Disk Graphs. These are geometric graphs such that for some positive integers l,k$l,k$ the following property holds at each node v$v$: if we partition the unit circle centered at v$v$ into 2k$2k$ equally sized wedges then each wedge can contain at most l$l$ points different from v$v$. We assume that the nodes are location aware, i.e. they know their Cartesian coordinates in the plane. The algorithm presented is local in the sense that each node can receive information emanating only from nodes which are at most a constant (depending on k$k$ and l$l$, but not on the size of the graph) number of hops (measured in the original underlying Unit Disk Graph) away from it, and hence the algorithm terminates in a constant number of steps. The number of colours used is 2kl+1$2kl+1$ and this is optimal for local algorithms (since the maximal degree is 2kl$2kl$ and a colouring with 2kl$2kl$ colours can only be constructed by a global algorithm), thus showing that in this class of graphs the price for locality is only one additional colour.     

A modified hidden Markov model

This paper considers two discrete time, finite state processes X$X$ and Y$Y$. In the usual hidden Markov model X$X$ modulates the values of Y$Y$. However, the values of Y$Y$ are then i.i.d. given X$X$. In this paper a new model is considered where the Markov chain X$X$ modulates the transition probabilities of the second, observed chain Y$Y$. This more realistically can represent problems arising in DNA sequencing. Algorithms for all related filters, smoothers and parameter estimations are derived. Versions of the Viterbi algorithms are obtained.     

An equation-based Heap Sizing Rule

For garbage-collected applications, dynamically-allocated objects are contained in a heap. Programmer productivity improves significantly if there is a garbage collector to automatically deallocate objects that are no longer needed by the applications. However, there is a run-time performance overhead in garbage collection, and this cost is sensitive to heap size H$H$: a smaller H$H$ will trigger more collection, but a large H$H$ can cause page faults, as when H$H$ exceeds the size M$M$ of main memory allocated to the application.