New algorithms for convex cost tension problem with application to computer vision

Motivated by various applications to computer vision, we consider the convex cost tension problem, which is the dual of the convex cost flow problem. In this paper, we first propose a primal algorithm for computing an optimal solution of the problem. Our primal algorithm iteratively updates primal variables by solving associated minimum cut problems. We show that the time complexity of the primal algorithm is $O(K?T(n,m))$, where $K$ is the range of primal variables and $T(n,m)$ is the time needed to compute a minimum cut in a graph with $n$ nodes and $m$ edges. We then develop an improved version of the primal algorithm, called the primal–dual algorithm, by making good use of dual variables in addition to primal variables. Although its time complexity is the same as that of the primal algorithm, we can expect a better performance in practice. We finally consider an application to a computer vision problem called the panoramic image stitching.     

Solving linear program as linear system in polynomial time

A physically concise polynomial-time iterative-cum-non-iterative algorithm is presented to solve the linear program (LP) $Min{c}^{t}x\text{subject to}Ax=b,x\ge 0$. The iterative part–a variation of Karmarkar projective transformation algorithm–is essentially due to Barnes only to the extent of detection of basic variables of the LP taking advantage of monotonic convergence. It involves much less number of iterations than those in the Karmarkar projective transformation algorithm. The shrunk linear system containing only the basic variables of the solution vector $x$ resulting from $Ax=b$ is then solved in the mathematically non-iterative part. The solution is then tested for optimality and is usually more accurate because of reduced computation and has less computational and storage complexity due to smaller order of the system. The computational complexity of the combination of these two parts of the algorithm is polynomial-time $O\left(n^3\right)$. The boundedness of the solution, multiple solutions, and no-solution (inconsistency) cases are discussed. The effect of degeneracy of the primal linear program and/or its dual on the uniqueness of the optimal solution is mentioned. The algorithm including optimality test is implemented in Matlab which is found to be useful for solving many real-world problems.     

Nonlinear Fourier transforms for the sine-Gordon equation in the quarter plane

Using the Unified Transform, also known as the Fokas method, the solution of the sine-Gordon equation in the quarter plane can be expressed in terms of the solution of a matrix Riemann–Hilbert problem whose definition involves four spectral functions $a,b,A,B$. The functions $a(k)$ and $b(k)$ are defined via a nonlinear Fourier transform of the initial data, whereas $A(k)$ and $B(k)$ are defined via a nonlinear Fourier transform of the boundary values. In this paper, we provide an extensive study of these nonlinear Fourier transforms and the associated eigenfunctions under weak regularity and decay assumptions on the initial and boundary values. The results can be used to determine the long-time asymptotics of the sine-Gordon quarter-plane solution via nonlinear steepest descent techniques.     

Gap vertex-distinguishing edge colorings of graphs

In this paper, we study a new coloring parameter of graphs called the gap vertex-distinguishing edge coloring. It consists in an edge-coloring of a graph $G$ which induces a vertex distinguishing labeling of $G$ such that the label of each vertex is given by the difference between the highest and the lowest colors of its adjacent edges. The minimum number of colors required for a gap vertex-distinguishing edge coloring of $G$ is called the gap chromatic number of $G$ and is denoted by $\mathrm{gap}\left(G\right)$.We here study the gap chromatic number for a large set of graphs $G$ of order $n$ and prove that $\mathrm{gap}\left(G\right)\in \{n?1,n,n+1\}$.     

Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs

An interval$t$-coloring of a multigraph $G$ is a proper edge coloring with colors $1,\dots ,t$ such that the colors of the edges incident with every vertex of $G$ are colored by consecutive colors. A cyclic interval$t$-coloring of a multigraph $G$ is a proper edge coloring with colors $1,\dots ,t$ such that the colors of the edges incident with every vertex of $G$ are colored by consecutive colors, under the condition that color $1$ is considered as consecutive to color $t$. Denote by $w\left(G\right)$ ($w_c\left(G\right)$) and $W\left(G\right)$ ($W_c\left(G\right)$) the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph $G$, respectively. We present some new sharp bounds on $w\left(G\right)$ and $W\left(G\right)$ for multigraphs $G$ satisfying various conditions. In particular, we show that if $G$ is a $2$-connected multigraph with an interval coloring, then $W\left(G\right)\le 1+?\frac{\left|V\left(G\right)\right|}{2}?(\Delta \left(G\right)?1)$. We also give several results towards the general conjecture that $W_c\left(G\right)\le \left|V\left(G\right)\right|$ for any triangle-free graph $G$ with a cyclic interval coloring; we establish that approximate versions of this conjecture hold for several families of graphs, and we prove that the conjecture is true for graphs with maximum degree at most $4$.     

The weighted 2-metric dimension of trees in the non-landmarks model

Let $T=(V,E)$ be a tree graph with non-negative costs defined on the vertices. A vertex $\tau$ is called a separating vertex for $u$ and $v$ if the distances of $\tau$ to $u$ and $v$ are not equal. A set of vertices $L\subseteq V$ is a feasible solution for the non-landmarks model (NL), if for every pair of distinct vertices, $u,v\in V\setminus L$, there are at least two vertices of $L$ separating them. Such a feasible solution is called a landmark set. We analyze the structure of landmark sets for trees and design a linear time algorithm for finding a minimum cost landmark set for a given tree graph.     

b-coloring of Kneser graphs

A $b$-coloring of a graph $G$ with $k$ colors is a proper coloring of $G$ using $k$ colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer $k$ for which $G$ has a $b$-coloring using $k$ colors is the $b$-chromatic number $b\left(G\right)$ of $G$. The $b$-spectrum $S_b\left(G\right)$ of a graph $G$ is the set of positive integers $k,\chi \left(G\right)\le k\le b\left(G\right)$, for which $G$ has a $b$-coloring using $k$ colors. A graph $G$ is $b$-continuous if $S_b\left(G\right)$ = the closed interval $[\chi \left(G\right),b\left(G\right)]$. In this paper, we obtain an upper bound for the $b$-chromatic number of some families of Kneser graphs. In addition we establish that $[\chi \left(G\right),n+k+1]?S_b\left(G\right)$ for the Kneser graph $G=K(2n+k,n)$ whenever $3\le n\le k+1$. We also establish the $b$-continuity of some families of regular graphs which include the family of odd graphs.     

List r-hued chromatic number of graphs with bounded maximum average degrees

For integers $k,r>0$, a $(k,r)$-coloring of a graph $G$ is a proper coloring $c$ with at most $k$ colors such that for any vertex $v$ with degree $d\left(v\right)$, there are at least min$\{d\left(v\right),r\}$ different colors present at the neighborhood of $v$. The $r$-hued chromatic number of $G$, ${\chi }_r\left(G\right)$, is the least integer $k$ such that a $(k,r)$-coloring of $G$ exists. The list$r$-hued chromatic number${\chi }_{L,r}\left(G\right)$ of $G$ is similarly defined. Thus if $\Delta \left(G\right)\ge r$, then ${\chi }_{L,r}\left(G\right)\ge {\chi }_r\left(G\right)\ge r+1$. We present examples to show that, for any sufficiently large integer $r$, there exist graphs with maximum average degree less than 3 that cannot be $(r+1,r)$-colored. We prove that, for any fraction $q<\frac{14}{5}$, there exists an integer $R=R\left(q\right)$ such that for each $r\ge R$, every graph $G$ with maximum average degree $q$ is list $(r+1,r)$-colorable. We present examples to show that for some $r$ there exist graphs with maximum average degree less than 4 that cannot be $r$-hued colored with less than $\frac{3r}{2}$ colors. We prove that, for any sufficiently small real number $?>0$, there exists an integer $h=h\left(?\right)$ such that every graph $G$ with maximum average degree $4??$ satisfies ${\chi }_{L,r}\left(G\right)\le r+h\left(?\right)$. These results extend former results in Bonamy et al. (2014).     

A note on two source location problems

We consider Source Location ($\mathsf{SL}$) problems: given a capacitated network $G=(V,E)$, cost $c(v)$ and a demand $d(v)$ for every $v\in V$, choose a min-cost $S\subseteq V$ so that $\lambda (v,S)⩾d(v)$ holds for every $v\in V$, where $\lambda (v,S)$ is the maximum flow value from v to S. In the directed variant, we have demands $d^{\mathit{in}}(v)$ and $d^{\mathit{out}}(v)$ and we require $\lambda (S,v)⩾d^{\mathit{in}}(v)$ and $\lambda (v,S)⩾d^{\mathit{out}}(v)$. Undirected $\mathsf{SL}$ is (weakly) NP-hard on stars with $r(v)=0$ for all v except the center. But, it is known to be polynomially solvable for uniform costs and uniform demands. For general instances, both directed an undirected $\mathsf{SL}$ admit a $(\ln D+1)$-approximation algorithms, where D is the sum of the demands; up to constant this is tight, unless P = NP. We give a pseudopolynomial algorithm for undirected $\mathsf{SL}$ on trees with running time $O(|V|{\Delta }^3)$, where $\Delta ={\max }_{v\in V}d(v)$. This algorithm is used to derive a linear time algorithm for undirected $\mathsf{SL}$ with $\Delta ⩽3$. We also consider the Single Assignment Source Location ($\mathsf{SASL}$) where every $v\in V$ should be assigned to a single node $s(v)\in S$. While the undirected $\mathsf{SASL}$ is in P, we give a $(\ln |V|+1)$-approximation algorithm for the directed case, and show that this is tight, unless P = NP.     

Online maximum k-coverage

We study an online model for the maximum $k$-vertex-coverage problem, in which, given a graph $G=(V,E)$ and an integer $k$, we seek a subset $A?V$ such that $\left|A\right|=k$ and the number of edges covered by $A$ is maximized. In our model, at each step $i$, a new vertex $v_i$ is released, and we have to decide whether we will keep it or discard it. At any time of the process, only $k$ vertices can be kept in memory; if at some point the current solution already contains $k$ vertices, any inclusion of a new vertex in the solution must entail the definite deletion of another vertex of the current solution (a vertex not kept when released is definitely deleted). We propose algorithms for several natural classes of graphs (mainly regular and bipartite), improving on an easy $\frac{1}{2}$-competitive ratio. We next settle a set version of the problem, called the maximum $k$-(set)-coverage problem. For this problem, we present an algorithm that improves upon former results for the same model for small and moderate values of $k$.     

On mixed codes with covering radius 1 and minimum distance 2: (extended abstract)

Let R, S and T be finite sets with $|R|=r$, $|S|=s$ and $|T|=t$. A code $C\subset R\times S\times T$ with covering radius 1 and minimum distance 2 is closely connected to a certain generalized partial Latin rectangle. We present various constructions of such codes and some lower bounds on their minimal cardinality $K(r,s,t;2)$. These bounds turn out to be best possible in many instances. Focussing on the special case $t=s$ we determine $K(r,s,s;2)$ when r divides s, when $r=s-1$, when s is large, relative to r, when r is large, relative to s, as well as $K(3r,2r,2r;2)$. Finally, a table with bounds on $K(r,s,s;2)$ is given.     

Injective choosability of subcubic planar graphs with girth 6

An injective coloring of a graph $G$ is an assignment of colors to the vertices of $G$ so that any two vertices with a common neighbor have distinct colors. A graph $G$ is injectively $k$-choosable if for any list assignment $L$, where $\left|L\left(v\right)\right|\ge k$ for all $v\in V\left(G\right)$, $G$ has an injective $L$-coloring. Injective colorings have applications in the theory of error-correcting codes and are closely related to other notions of colorability. In this paper, we show that subcubic planar graphs with girth at least 6 are injectively 5-choosable. This strengthens the result of Lu?ar, ?krekovski, and Tancer that subcubic planar graphs with girth at least 7 are injectively 5-colorable. Our result also improves several other results in particular cases.     

Global existence to the initial–boundary value problem for a system of nonlinear diffusion and wave equations

We prove the global existence of weak solution pair to the initial boundary value problem for a system of m-Laplacian type diffusion equation and nonlinear wave equation. The interaction of two equations is given through nonlinear source terms $f(u,v)$ and $g(u,v)$.     

Improved Cotlar's inequality in the context of local Tb theorems

In the context of local Tb theorems with $L^p$ testing conditions we prove an enhanced Cotlar's inequality. This is related to the problem of removing the so called buffer assumption of Hytönen–Nazarov, which is the final barrier for the full solution of S. Hofmann's problem. We also investigate the problem of extending the Hytönen–Nazarov result to non-homogeneous measures. We work not just with the Lebesgue measure but with measures μ in ${\mathbb{R}}^d$ satisfying $\mu (B(x,r))\le C{r}^n$, $n\in (0,d]$. The range of exponents in the Cotlar type inequality depend on n. Without assuming buffer we get the full range of exponents $p,q\in (1,2]$ for measures with $n\le 1$, and in general we get $p,q\in [2??(n),2]$, $?(n)>0$. Consequences for (non-homogeneous) local Tb theorems are discussed.     

Explicit solutions for one-dimensional two-phase free boundary problems with either shrinkage or expansion

We consider a one-dimensional solidification of a pure substance which is initially in liquid state in a bounded interval $[0,l]$. Initially, the liquid is above the freezing temperature, and cooling is applied at $x=0$ while the other end $x=l$ is kept adiabatic. At the time $t=0$, the temperature of the liquid at $x=0$ comes down to the freezing point and solidification begins, where $x=s\left(t\right)$ is the position of the solid–liquid interface. As the liquid solidifies, it shrinks ($0<r<1$) or expands ($r<0$) and appears a region between $x=0$ and $x=rs\left(t\right)$, with $r<1$. Temperature distributions of the solid and liquid phases and the position of the two free boundaries ($x=rs\left(t\right)$ and $x=s\left(t\right)$) in the solidification process are studied. For three different cases, changing the condition on the free boundary $x=rs\left(t\right)$ (temperature boundary condition, heat flux boundary condition and convective boundary condition) an explicit solution is obtained. Moreover, the solution of each problem is given as a function of a parameter which is the unique solution of a transcendental equation and for two of the three cases a condition on the parameter must be verified by data of the problem in order to have an instantaneous phase-change process. In all the cases, the explicit solution is given by a representation of the similarity type.     

On a conjecture about orders of products of elements in the symmetric group

For any $a,b,c,n\in \mathbb{N}$ with $1<a,b,c\le n?2$, then there exist $\alpha ,\beta \in S_n$ such that $o(\alpha )=a$, $o(\beta )=b$ and $o(\alpha \beta )=c$. This is a conjecture of Stefan Kohl and which is closely related to problem on covers of the complex projective line. In this note we prove the conjecture is true.