Edge-fault-tolerant pancyclicity and bipancyclicity of Cartesian product graphs with faulty edges

Let r≥ 4 be an even integer. Graph G is r-bipancyclic if it contains a cycle of every even length from r to $2\lfloor \frac{n(G)}{2}\rfloor$, where $n(G)$ is the number of vertices in G. A graph G is r-pancyclic if it contains a cycle of every length from r to $n(G)$, where $r\ge 3$. A graph is k-edge-fault Hamiltonian if, after deleting arbitrary k edges from the graph, the resulting graph remains Hamiltonian. The terms k-edge-fault r-bipancyclic and k-edge-fault r-pancyclic can be defined similarly. Given two graphs G and H, where $n(G)$, $n(H)\ge$ 9, let $k_1$, $k_2\ge 5$ be the minimum degrees of G and H, respectively. This study determined the edge-fault r-bipancyclic and edge-fault r-pancyclic of Cartesian product graph $G\times H$ with some conditions. These results were then used to evaluate the edge-fault pancyclicity (bipancyclicity) of ${\mathit{NQ}}_{m_r,\dots ,m_1}$ and ${\mathit{GQ}}_{m_r,\dots ,m_1}$.     

Approximation algorithms for the Weighted t-Uniform Sparsest Cut and some other graph partitioning problems

We study the Weighted t-Uniform Sparsest Cut (Weighted t-USC) and other related problems. In an instance of the Weighted t-USC problem, a parameter t and an undirected graph $G=(V,E)$ with edge-weights $w:E\to {\mathbb{R}}_{\ge 0}$ and vertex-weights $\eta :V\to {\mathbb{R}}_{+}$ are given. The goal is to find a vertex set $S\subseteq V$ with $|S|\le t$ while minimizing $w(S,V\backslash S)/\eta (S)$, where $w(S,V\backslash S)$ is the total weight of the edges with exactly one endpoint in S and $\eta (S)={\sum }_{v\in S}\eta (v)$. For this problem, we present a $(O(\log t),1+ϵ)$ factor bicriteria approximation algorithm. Our algorithm outperforms the current best algorithm when $t=n^{o(1)}$. We also present better approximation algorithms for Weighted ρ-Unbalanced Cut and Min–Max k-Partitioning problems.     

On the applicability of Postʼs lattice

For decision problems $\Pi (B)$ defined over Boolean circuits using gates from a restricted set B only, we have $\Pi (B){?}_m^{{\mathrm{AC}}^0}\Pi (B^{\prime })$ for all finite sets B and $B^{\prime }$ of gates such that all gates from B can be computed by circuits over gates from $B^{\prime }$. In this note, we show that a weaker version of this statement holds for decision problems defined over Boolean formulae, namely that $\Pi (B){?}_m^{{\mathrm{NC}}^2}\Pi (B^{\prime }\cup \{\wedge ,\vee \})$ and $\Pi (B){?}_m^{{\mathrm{NC}}^2}\Pi (B^{\prime }\cup \{0,1\})$ for all finite sets B and $B^{\prime }$ of Boolean functions such that all $f\in B$ can be defined in $B^{\prime }$.     

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.     

Efficient algorithms for the round-trip 1-center and 1-median problems

This paper presents improved algorithms for the round-trip single-facility location problem on a general graph, in which a set A of collection depots is given and the service distance of a customer is defined to be the distance from the server, to the customer, then to a depot, and back to the server. Each customer i is associated with a subset $A^i\subseteq A$ of depots that i can potentially select from and use. When $A^i=A$ for each customer i, the problem is unrestricted; otherwise it is restricted. For the restricted round-trip 1-center problem, we give an $O(mn\lg n)$-time algorithm. For the restricted 1-median problem, we give an $O(mn\lg (|A|/m)+n^2\lg n)$-time algorithm. For the unrestricted 1-median problem, we give an $O(mn+n^2\lg \lg n)$-time algorithm.     

Deterministic extractors for small-space sources

We give polynomial-time, deterministic randomness extractors for sources generated in small space, where we model space s sources on ${\{0,1\}}^n$ as sources generated by width $2^s$ branching programs. Specifically, there is a constant $\eta >0$ such that for any $\zeta >n^{?\eta }$, our algorithm extracts $m=(\delta ?\zeta )n$ bits that are exponentially close to uniform (in variation distance) from space s sources with min-entropy δn, where $s=\Omega ({\zeta }^{3}n)$. Previously, nothing was known for $\delta ?1/2$, even for space 0. Our results are obtained by a reduction to the class of total-entropy independent sources. This model generalizes both the well-studied models of independent sources and symbol-fixing sources. These sources consist of a set of r independent smaller sources over ${\{0,1\}}^{?}$, where the total min-entropy over all the smaller sources is k. We give deterministic extractors for such sources when k is as small as $\mathsf{polylog}(r)$, for small enough ?.     

Pancyclic out-arcs of a vertex in oriented graphs

Let D be an oriented graph with $n?9$ vertices and minimum degree at least $n?2$, such that, for any two vertices x and y, either x dominates y or $d_D^{+}(x)+d_D^{?}(y)?n?3$. Song (1994) [5] proved that D is pancyclic. Bang-Jensen and Guo (1999) [2] proved, based on Song?s result, that D is vertex pancyclic. In this article, we give a sufficient condition for D to contain a vertex whose out-arcs are pancyclic in D, when $n?14$.