Longest paths and cycles in faulty star graphs

In this paper, we investigate the star graph $S_n$ with faulty vertices and/or edges from the graph theoretic point of view. We show that between every pair of vertices with different colors in a bicoloring of $S_n$, $n⩾4$, there is a fault-free path of length at least $n!-2f_v-1$, and there is a path of length at least $n!-2f_v-2$ joining a pair of vertices with the same color, when the number of faulty elements is $n-3$ or less. Here, $f_v$ is the number of faulty vertices. $S_n$, $n⩾4$, with at most $n-2$ faulty elements has a fault-free cycle of length at least $n!-2f_v$ unless the number of faulty elements are $n-2$ and all the faulty elements are edges incident to a common vertex. It is also shown that $S_n$, $n⩾4$, is strongly hamiltonian-laceable if the number of faulty elements is $n-3$ or less and the number of faulty vertices is one or less.     

A direct solver with reutilization of LU factorizations for h-adaptive finite element grids with point singularities

This paper describes a direct solver algorithm for a sequence of finite element meshes that are $h$-refined towards one or several point singularities. For such a sequence of grids, the solver delivers linear computational cost $O\left(N\right)$ in terms of CPU time and memory with respect to the number of unknowns $N$. The linear computational cost is achieved by utilizing the recursive structure provided by the sequence of $h$-adaptive grids with a special construction of the elimination tree that allows for reutilization of previously computed partial LU (or Cholesky) factorizations over the entire unrefined part of the computational mesh. The reutilization technique reduces the computational cost of the entire sequence of $h$-refined grids from $O\left(N^2\right)$ down to $O\left(N\right)$. Theoretical estimates are illustrated with numerical results on two- and three-dimensional model problems exhibiting one or several point singularities.     

A proof of the extended Duval's conjecture

We give a short and elementary proof of the following stronger version of Duval's conjecture: let u be an unbordered word, and $v$ a word of length $\left|u\right|-1$, such that $v$ is not a prefix of u. Then u$v$ contains an unbordered word of length at least $\left|u\right|+1$.     

Scheduling directed a-cyclic task graphs on a bounded set of heterogeneous processors using task duplication

In a distributed computing environment, the schedule by which tasks are assigned to processors is critical to minimizing the overall run-time of the application. However, the problem of discovering the schedule that gives the minimum finish time is NP-Complete. This paper addresses static scheduling of a directed a-cyclic task graph (DAG) on a heterogeneous, bounded set of distributed processors to minimize the makespan. By combining several innovative techniques, including insertion-based scheduling and multiple task duplication, we present a new heuristic, known as Heterogeneous N-predecessor Decisive Path (HNDP), for scheduling directed a-cyclic weighted task graphs (DAGs) on a set of heterogeneous processors. We compare the performance of HNDP, under a range of varying input conditions, with two of the best existing heterogeneous heuristics namely HEFT and STDS. The results presented in this paper show that HNDP outperforms the two heuristics in terms of finish time and the number of processors employed over a wide range of parameters. The complexity of HNPD is $O(v^{2.}p)$ vs. $O(v^{2.}p)$ of HEFT and $O(v^2)$ of STDS where $v$ is the number of nodes in the DAG.     

Long time stability and convergence rate of MacCormack rapid solver method for nonstationary Stokes–Darcy problem

We propose and study a combination of two second-order implicit–explicit (IMEX) methods for the coupled Stokes–Darcy system that governs flows in karst aquifers. The first is a second-order explicit two-step MacCormack scheme and the second is a second-order implicit Crank–Nicolson method. Both algorithms only require the solution of two decoupled problems at each time step, one Stokes and the other Darcy. This combination so called the MacCormack rapid solver method is very efficient (faster, at least of second order accuracy in time and space) and can be easily implemented using legacy codes. Under time step limitation of the form $\Delta t\le Ch$ (where $h,$$\Delta t$ are mesh size and time step, respectively, and $C$ is a physical parameter) we prove both long time stability and the rate of convergence of the method. Some numerical experiments are presented and discussed.     

Inhomogeneous Dirichlet boundary condition in the a posteriori error control of the obstacle problem

We study a posteriori error control of finite element approximation of the elliptic obstacle problem with nonhomogeneous Dirichlet boundary condition. The results in the article are two fold. Firstly, we address the influence of the inhomogeneous Dirichlet boundary condition in residual based a posteriori error control of the elliptic obstacle problem. Secondly by rewriting the obstacle problem in an equivalent form, we derive a posteriori error bounds which are in simpler form and efficient. To accomplish this, we construct and use a post-processed solution ${\stackrel{?}{u}}_h$ of the discrete solution $u_h$ which satisfies the exact boundary conditions sharply although the discrete solution $u_h$ may not satisfy. We propose two post processing methods and analyze them, namely the harmonic extension and a linear extension. The theoretical results are illustrated by the numerical results.     

Proximity and average eccentricity of a graph

Let $G=(V,E)$ be a connected graph on n vertices. The proximity $\pi (G)$ of G is the minimum average distance from a vertex of G to all others. The eccentricity $e(v)$ of a vertex v in G is the largest distance from v to another vertex, and the average eccentricity $\mathit{ecc}(G)$ of the graph G is $\frac{1}{n}{\sum }_{v\in V(G)}e(v)$. Recently, it was conjectured by Aouchiche and Hansen (2011) [3] that for any connected graph G on $n?3$ vertices, $\mathit{ecc}(G)?\pi (G)?\mathit{ecc}(P_n)?\pi (P_n)$, with equality if and only if $G?P_n$. In this paper, we show that this conjecture is true.