A Schnyder wood is an orientation and coloring of the edges of a planar map
satisfying a simple local property. We propose a generalization of Schnyder
woods to toroidal maps with application to graph drawing. We prove the
existence of these Schnyder woods for toroidal triangulations. We show that
Schnyder woods can be used to embed the universal cover of a toroidal map on an
infinite and periodic orthogonal surface. Finally we use this embedding to
obtain a straight-line flat torus representation of any toroidal map in a
polynomial size grid.

We introduce a new geometric approach to Sturmian words by means of a mapping
that associates certain lines in the n x n -grid and sets of finite Sturmian
words of length n. Using this mapping, we give new proofs of the formulas
enumerating the finite Sturmian words and the palindromic finite Sturmian words
of a given length. We also give a new proof for the well-known result that a
factor of a Sturmian word has precisely two return words.

We consider the problem of balancing load items (tokens) on networks.
Starting with an arbitrary load distribution, we allow in each round nodes to
exchange tokens with their neighbors. The goal is to achieve a distribution
where all nodes have nearly the same number of tokens.

In this paper, we obtain complete characterization for nested canalyzing
functions (NCFs) by obtaining its unique algebraic normal form (polynomial
form). We introduce a new concept, LAYER NUMBER for NCF. Based on this, we
obtain explicit formulas for the the following important parameters: 1) Number
of all the nested canalyzing functions, 2) Number of all the NCFs with given
LAYER NUMBER, 3) Hamming weight of any NCF, 4) The activity number of any
variable of any NCF, 5) The average sensitivity of any NCF.

Although models are built on the basis of some observations of reality, the
concepts that derive theoretically from their definitions as well as from their
characteristics and properties are not necessarily direct consequences of these
initial observations. Indeed, many of them rather follow from chains of
theoretical inferences that are only based on the precise model definitions and
rely strongly, in addition, on some consequential working hypotheses.

The palindromization map $\psi$ in a free monoid $A^*$ was introduced in 1997
by the first author in the case of a binary alphabet $A$, and later extended by
other authors to arbitrary alphabets. Acting on infinite words, $\psi$
generates the class of standard episturmian words, including standard
Arnoux-Rauzy words.

In this paper we generalize the palindromization map, starting with a given
code $X$ over $A$. The new map $\psi_X$ maps $X^*$ to the set $PAL$ of
palindromes of $A^*$. In this way some properties of $\psi$ are lost and some
are saved in a weak form.

A Sierpinski number is an odd positive integer, k, such that no positive
integer of the form k * 2^n + 1 is prime. Similar to a Sierpinski number, a
Riesel number is an odd positive integer, k, such that no positive integer of
the form k * 2^n + 1 is prime. A cover for such a k is a finite list of
positive integers such that each integer j of the appropriate form has a
factor, d, in the cover, with 1 < d < j. Given a k and its cover, ACL2 is used
to systematically verify that each integer of the given form has a non-trivial
factor in the cover.

The traditional axiomatic approach to voting is motivated by the problem of
reconciling differences in subjective preferences. In contrast, a dominant line
of work in the theory of voting over the past 15 years has considered a
different kind of scenario, also fundamental to voting, in which there is a
genuinely "best" outcome that voters would agree on if they only had enough
information.

At some places (see the references) Martin Erickson describes a certain game:

"Two players alternately write O's (first player) and X's (second player) in
the unoccupied cells of an n x n grid. The first player (if any) to occupy four
cells at the vertices of a square with horizontal and vertical sides is the
winner."

Then he asks "What is the outcome of the game given optimal play?" or

"What is the smallest n such that the first player has a winning strategy?"

For n lower than 3 a win is obviously impossible.

Eigenvector localization refers to the situation when most of the components
of an eigenvector are zero or near-zero. This phenomenon has been observed on
eigenvectors associated with extremal eigenvalues, and in many of those cases
it can be meaningfully interpreted in terms of "structural heterogeneities" in
the data.

In the past few decades there has been a good deal of papers which are
concerned with optimization problems in different areas of mathematics (along
0-1 words, finite or infinite) and which yield - sometimes quite unexpectedly -
balanced words as optimal. In this note we list some key results along these
lines known to date.

Given a countable set X (usually taken to be the natural numbers or
integers), an infinite permutation, \pi, of X is a linear ordering of X. This
paper investigates the combinatorial complexity of infinite permutations on the
natural numbers associated with the image of uniformly recurrent aperiodic
binary words under the letter doubling map. An upper bound for the complexity
is found for general words, and a formula for the complexity is established for
the Sturmian words and the Thue-Morse word.

In a previous paper, we described the set of words that appear in the coding
of smooth (resp. analytic) curves at arbitrary small scale. The aim of this
paper is to compute the complexity of those languages.

Partial words are sequences over a finite alphabet that may contain wildcard
symbols, called holes, which match or are compatible with all letters; partial
words without holes are said to be full words (or simply words). Given an
infinite partial word w, the number of distinct full words over the alphabet
that are compatible with factors of w of length n, called subwords of w, refers
to a measure of complexity of infinite partial words so-called subword
complexity.

Randomized techniques play a fundamental role in theoretical computer science
and discrete mathematics, in particular for the design of efficient algorithms
and construction of combinatorial objects. The basic goal in derandomization
theory is to eliminate or reduce the need for randomness in such randomized
constructions. In this thesis, we explore some applications of the fundamental
notions in derandomization theory to problems outside the core of theoretical
computer science, and in particular, certain problems related to coding theory.

We explore the geometry of complex networks in terms of an n-dimensional
Euclidean embedding represented by the Moore-Penrose pseudo-inverse of the
graph Laplacian $(\bb L^+)$. The squared distance of a node $i$ to the origin
in this n-dimensional space $(l^+_{ii})$, yields a structural centrality index
$(\mathcal{C}^{*}(i) = 1/l^+_{ii})$ for node $i$. In turn, the sum of
reciprocals of individual node structural centralities,
$\sum_{i}1/\mathcal{C}^*(i) = \sum_{i} l^+_{ii}$, i.e.

The extension complexity of a polytope $P$ is the smallest integer $k$ such
that $P$ is the projection of a polytope $Q$ with $k$ facets. We study the
extension complexity of $n$-gons in the plane. First, we give a new proof that
the extension complexity of regular $n$-gons is $O(\log n)$, a result
originating from work by Ben-Tal and Nemirovski (2001). Our proof easily
generalizes to other permutahedra and simplifies proofs of recent results by
Goemans (2009), and Kaibel and Pashkovich (2011). Second, we prove a lower
bound of $\sqrt{2n}$ on the extension complexity of generic $n$-gons.

Recently there has been much interest in "sparsifying" sums of rank one
matrices: modifying the coefficients such that only a few are nonzero, while
approximately preserving the matrix that results from the sum. Results of this
sort have found applications in many different areas, including sparsifying
graphs. In this paper we consider the more general problem of sparsifying sums
of positive semidefinite matrices. We give several algorithms for solving this
problem and describe several applications of these algorithms.

Alternative novel measures of the distance between any two partitions of a
n-set are proposed and compared, together with a main existing one, namely
'partition-distance' D(.,.). The comparison achieves by checking their
restriction to modular elements of the partition lattice, as well as in terms
of suitable classifiers. Two of the new measures obtain through the size, a
function mapping every partition into the number of atoms finer than that
partition.

Graham and Sloane proposed in 1980 a conjecture stating that every tree has a
harmonious labelling, a graph labelling closely related to additive base. Very
limited results on this conjecture are known. In this paper, we proposed a
computational approach to this conjecture by checking trees with limited size.
With a hybrid algorithm, we are able to show that every tree with at most 31
nodes is graceful, extending the best previous result in this direction.

In this work we study the polytope associated with a 0/1 integer programming
formulation for the Equitable Coloring Problem. We find several families of
valid inequalities and derive sufficient conditions in order to be
facet-defining inequalities. We also present computational evidence of the
effectiveness of including these inequalities as cuts in a Branch & Cut
algorithm.

The cops and robbers game has been extensively studied under the assumption
of optimal play by both the cops and the robbers. In this paper we study the
problem in which cops are chasing a drunk robber (that is, a robber who
performs a random walk) on a graph. Our main goal is to characterize the "cost
of drunkenness." Specif?ically, we study the ratio of expected capture times
for the optimal version and the drunk robber one. We also examine the
algorithmic side of the problem; that is, how to compute near-optimal search
schedules for the cops.

In this paper, we look at the improvement of our knowledge on a family of
tilings of the hyperbolic plane which is brought in by the use of Sergeyev's
numeral system based on grossone. It appears that the information we can get by
using this new numeral system depends on the way we look at the tilings. The
ways are significantly different but they confirm some results which were
obtained in the traditional but constructive frame and allow us to obtain an
additional precision with respect to this information.

Clique separator decomposition introduced by Tarjan and Whitesides is one of
the most important graph decompositions. A graph is an {\em atom} if it has no
clique separator. A {\em hole} is a chordless cycle with at least five
vertices, and an {\em antihole} is the complement graph of a hole. A graph is
{\em weakly chordal} if it is hole- and antihole-free. $K_4-e$ is also called
{\em diamond}. {\em Paraglider} has five vertices four of which induce a
diamond, and the fifth vertex sees exactly the two vertices of degree two in
the diamond.

A graph $G$ is called a pairwise compatibility graph (PCG) if there exists an
edge weighted tree $T$ and two non-negative real numbers $d_{min}$ and
$d_{max}$ such that each leaf $l_u$ of $T$ corresponds to a vertex $u \in V$
and there is an edge $(u,v) \in E$ if and only if $d_{min} \leq d_T (l_u, l_v)
\leq d_{max}$ where $d_T (l_u, l_v)$ is the sum of the weights of the edges on
the unique path from $l_u$ to $l_v$ in $T$. In this paper we analyze the class
of PCG in relation with two particular subclasses resulting from the the cases
where $\dmin=0$ (LPG) and $\dmax=+\infty$ (mLPG).

A path in an edge colored graph is said to be a rainbow path if no two edges
on the path have the same color. An edge colored graph is (strongly) rainbow
connected if there exists a (geodesic) rainbow path between every pair of
vertices. The (strong) rainbow connectivity of a graph $G$, denoted by
($src(G)$, respectively) $rc(G)$ is the smallest number of colors required to
edge color the graph such that the graph is (strongly) rainbow connected. In
this paper, we show that for every $k \geq 3$, it is NP-hard to decide whether
$src(G) \leq k$ even when the graph $G$ is bipartite.

A $k$-L(2,1)-labeling of a graph is a function from its vertex set into the
set $\{0,...,k\}$, such that the labels assigned to adjacent vertices differ by
at least 2, and labels assigned to vertices of distance 2 are different. It is
known that finding the smallest $k$ admitting the existence of a
$k$-L(2,1)-labeling of any given graph is NP-Complete.

Given three permutations on the integers 1 through n, consider the set system
consisting of each interval in each of the three permutations. Jozsef Beck
conjectured (c. 1987) that the discrepancy of this set system is O(1). We give
a counterexample to this conjecture: for any positive integer n = 3^k, we
exhibit three permutations whose corresponding set system has discrepancy
Omega(log(n)). Our counterexample is based on a simple recursive construction,
and our proof of the discrepancy lower bound is by induction.

In a well-known paper[ARV], Arora, Rao and Vazirani obtained an O(sqrt(log
n)) approximation to the Balanced Separator problem and Uniform Sparsest Cut.
At the heart of their result is a geometric statement about sets of points that
satisfy triangle inequalities, which also underlies subsequent work on
approximation algorithms and geometric embeddings.

In this note, we give an equivalent formulation of the Structure theorem in
[ARV] in terms of the expansion of large sets in geometric graphs on sets of
points satisfying triangle inequalities.

As proved by Kahn, the chromatic number and fractional chromatic number of a
line graph agree asymptotically. That is, for any line graph $G$ we have
$\chi(G) \leq (1+o(1))\chi_f(G)$. We extend this result to quasi-line graphs,
an important subclass of claw-free graphs. Furthermore we prove that we can
construct a colouring that achieves this bound in polynomial time, giving us an
asymptotic approximation algorithm for the chromatic number of quasi-line
graphs.

A perfect matching in a $4$-uniform hypergraph is a subset of
$\lfloor\frac{n}{4}\rfloor$ disjoint edges. We prove that if $H$ is a
sufficiently large $4$-uniform hypergraph on $n=4k$ vertices such that every
vertex belongs to more than ${n-1\choose 3} - {3n/4 \choose 3}$ edges then $H$
contains a perfect matching. This bound is tight and settles a conjecture of
H{\'a}n, Person and Schacht.

We consider a the minimum k-way cut problem for unweighted graphs with a size
bound s on the number of cut edges allowed. Thus we seek to remove as few edges
as possible so as to split a graph into k components, or report that this
requires cutting more than s edges. We show that this problem is
fixed-parameter tractable (FPT) in s. More precisely, for s=O(1), our algorithm
runs in quadratic time while we have a different linear time algorithm for
planar graphs and bounded genus graphs. Our tractability result stands in
contrast to known W[1] hardness of related problems.

A directed graph is called Eulerian, if it contains a walk that traverses
every arc in the graph exactly once. We study the problem of Eulerian Extension
(EE) where a directed multigraph G and a weight function is given and it is
asked whether G can be made Eulerian by adding arcs whose total weight does not
exceed a given threshold. This problem is motivated through applications in
vehicle routing and flowshop scheduling. However, EE is NP- hard and thus we
use the parameterized complexity framework to analyze it.

Hypercontractive inequalities are a useful tool in dealing with extremal
questions in the geometry of high-dimensional discrete and continuous spaces.
In this survey we trace a few connections between different manifestations of
hypercontractivity, and also present some relatively recent applications of
these techniques in computer science.

Given n >= 4 positive real numbers, we prove in this note that they are the
face areas of a convex polyhedron if and only if the largest number is not more
than the sum of the others.

For integers k>0 and r>0, a conditional (k,r)-coloring of a graph G is a
proper k-coloring of the vertices of G such that every vertex v of degree d(v)
in G is adjacent to vertices with at least min{r,d(v)} different colors. The
smallest integer k for which a graph G has a conditional (k,r)-coloring is
called the rth order conditional chromatic number, denoted by $\chi_r(G)$.

Michael Hochman showed that every 1D effectively closed subshift can be
simulated by a 3D subshift of finite type and asked whether the same can be
done in 2D. It turned out that the answer is positive and necessary tools were
already developed in tilings theory. We discuss two alternative approaches:
first, developed by N. Aubrun and M. Sablik, goes back to Leonid Levin; the
second one, developed by the authors, goes back to Peter Gacs.

This paper studies two kinds of simulation between cellular automata:
simulations based on factor and simulations based on sub-automaton. We show
that these two kinds of simulation behave in two opposite ways with respect to
the complexity of attractors and factor subshifts. On the one hand, the factor
simulation preserves the complexity of limits sets or column factors (the
simulator CA must have a higher complexity than the simulated CA).

One of the most important open problems in machine scheduling is the problem
of scheduling a set of jobs on unrelated machines to minimize the makespan. The
best known approximation algorithm for this problem guarantees an approximation
factor of 2. It is known to be NP-hard to approximate with a better ratio than
3/2. Closing this gap has been open for over 20 years. The best known
approximation factors are achieved by LP-based algorithms. The strongest known
linear program formulation for the problem is the configuration-LP.

A D2CS of a graph G is a set $S \subseteq V(G)$ with $diam(G[S]) \leq 2$. We
study the problem of counting and enumerating D2CS of a graph. First we give an
explicit formula for the number of D2CS in a complete k-ary tree, Fibonacci
tree, binary Fibonacci tree and the binomial tree. Next we give an algorithm
for enumerating and counting D2CS of a graph. We then give a linear time
algorithm for finding all maximal D2CS in a strongly chordal graph.

The {\em packing chromatic number} $\chi_{\rho}(G)$ of a graph $G$ is the
least integer $k$ for which there exists a mapping $f$ from $V(G)$ to
$\{1,2,...,k\}$ such that any two vertices of color $i$ are at distance at
least $i+1$. This paper studies the packing chromatic number of infinite
distance graphs $G(\mathbb{Z},D)$, i.e. graphs with the set $\mathbb{Z}$ of
integers as vertex set, with two distinct vertices $i,j\in \mathbb{Z}$ being
adjacent if and only if $|i-j|\in D$.

The Generalized Discretizable Molecular Distance Geometry Problem is a
distance geometry problems that can be solved by a combinatorial algorithm
called ``Branch-and-Prune''. It was observed empirically that the number of
solutions of YES instances is always a power of two. We give a proof that this
event happens with probability one.

In this paper, we provide a novel matrix-analytic approach for studying
doubly exponential solution of randomized load balancing models (also known as
the supermarket models) with Markovian arrival processes (MAPs) and PH service
times. We describe the supermarket model as a system of differential vector
equations, and obtain a close-form solution: doubly exponential structure, for
the fixed point of the system of differential vector equations.

The notions of universality and completeness are central in the theories of
computation and computational complexity. However, proving lower bounds and
necessary conditions remains hard in most of the cases. In this article, we
introduce necessary conditions for a cellular automaton to be "universal",
according to a precise notion of simulation, related both to the dynamics of
cellular automata and to their computational power. This notion of simulation
relies on simple operations of space-time rescaling and it is intrinsic to the
model of cellular automata.

What does a typical road network look like? Existing generative models tend
to focus on one aspect to the exclusion of others. We introduce the
general-purpose \emph{quadtree model} and analyze its shortest paths and
maximum flow.

We give an algorithm to route a multicommodity flow in a planar graph $G$
with congestion $O(\log k)$, where $k$ is the maximum number of terminals on
the boundary of a face, when each demand edge lie on a face of $G$. We also
show that our specific method cannot achieve a substantially better congestion.

Let $\gamma'_s(G)$ be the signed edge domination number of G. In 2006, Xu
conjectured that: for any $2$-connected graph G of order $ n (n \geq 2),$
$\gamma'_s(G)\geq 1$. In this article we show that this conjecture is not true.
More precisely, we show that for any positive integer $m$, there exists an
$m$-connected graph $G$ such that $ \gamma'_s(G)\leq -\frac{m}{6}|V(G)|.$ Also
for every two natural numbers $m$ and $n$, we determine $\gamma'_s(K_{m,n})$,
where $K_{m,n}$ is the complete bipartite graph with part sizes $m$ and $n$.

A \textit{maximum stable set} in a graph $G$ is a stable set of maximum
cardinality. $S$ is a \textit{local maximum stable set} of $G$, and we write
$S\in\Psi(G)$, if $S$ is a maximum stable set of the subgraph induced by $S\cup
N(S)$, where $N(S)$ is the neighborhood of $S$. Nemhauser and Trotter Jr.
(1975), proved that any $S\in\Psi(G)$ is a subset of a maximum stable set of
$G$. In (Levit & Mandrescu, 2002) we have shown that the family $\Psi(T)$ of a
forest $T$ forms a greedoid on its vertex set.

We obtain improved upper bounds and new lower bounds on the chromatic number
as a linear function of the clique number, for the intersection graphs (and
their complements) of finite families of translates and homothets of a convex
body in $\RR^n$.

An $acyclic$ edge coloring of a graph is a proper edge coloring such that
there are no bichromatic cycles. The \emph{acyclic chromatic index} of a graph
is the minimum number k such that there is an acyclic edge coloring using k
colors and is denoted by $a'(G)$. It was conjectured by Alon, Sudakov and Zaks
(and much earlier by Fiamcik) that $a'(G)\le \Delta+2$, where $\Delta
=\Delta(G)$ denotes the maximum degree of the graph.

A new floating-point arithmetic called precision arithmetic is developed to
track precision for arithmetic calculations. It uses a novel rounding scheme to
avoid excessive rounding error propagation of conventional floating-point
arithmetic. Unlike interval arithmetic, its uncertainty tracking is based on
statistics and its bounding range is much tighter. Generic standards and
systematic methods for validating uncertainty-bearing arithmetics are
discussed. The precision arithmetic is found to be better than interval
arithmetic in uncertainty-tracking for linear algorithms.

It is proven that the connected pathwidth of any graph $G$ is at most
$2pw(G)+1$, where $pw(G)$ is the pathwidth of $G$. The method is constructive,
i.e. it yields an efficient algorithm that for a given path decomposition of
width $k$ computes a connected path decomposition of width at most $2k+1$. The
running time of the algorithm is $O(dk^2)$, where $d$ is the number of `bags'
in the input path decomposition.

A graph with at most two vertices of the same degree is called antiregular
(Merris 2003), maximally nonregular (Zykov 1990) or quasiperfect (Behzad,
Chartrand 1967). If s_{k} is the number of independent sets of cardinality k in
a graph G, then I(G;x) = s_{0} + s_{1}x + ... + s_{alpha}x^{alpha} is the
independence polynomial of G (Gutman, Harary 1983), where alpha = alpha(G) is
the size of a maximum independent set. In this paper we derive closed formulae
for the independence polynomials of antiregular graphs.

A joint characterisation of the observability and controllability of a
particular kind of discrete system has been developed. The key idea of the
procedure can be reduced to a correct choice of the sampling sequence. This
freedom, owing to the arbitrary choice of the sampling instants, is used to
improve the sensitivity of system observability and controllability, by
exploiting an adequate geometric structure. Some qualitative examples are
presented for illustrative purposes.

A general input-output modelling technique for aperiodic-sampling linear
systems has been developed. The procedure describes the dynamics of the system
and includes the sequence of sampling periods among the variables to be
handled. Some restrictive conditions on the sampling sequence are imposed in
order to guarantee the validity of the model. The particularization to the
periodic case represents an alternative to the classic methods of
discretization of continuous systems without using the Z-transform.

In Graph Minors III, Robertson and Seymour write:"It seems that the
tree-width of a planar graph and the tree-width of its geometric dual are
approximately equal - indeed, we have convinced ourselves that they differ by
at most one." They never gave a proof of this. In this paper, we prove that
given a hypergraph H on a surface of Euler genus k, the tree-width of H^* is at
most the maximum of tw(H)+1+k and the maximum size of a hyperedge of H^* minus
one.

Recently Byrka, Grandoni, Rothvoss and Sanita (at STOC 2010) gave a
1.39-approximation for the Steiner tree problem, using a hypergraph-based
linear programming relaxation. They also upper-bounded its integrality gap by
1.55. We describe a shorter proof of the same integrality gap bound, by
applying some of their techniques to a randomized loss-contracting algorithm.

Consider a class of decomposable combinatorial structures, using different
types of atoms $\Atoms = \{\At_1,\ldots ,\At_{|{\Atoms}|}\}$. We address the
random generation of such structures with respect to a size $n$ and a targeted
distribution in $k$ of its \emph{distinguished} atoms. We consider two
variations on this problem. In the first alternative, the targeted distribution
is given by $k$ real numbers $\TargFreq_1, \ldots, \TargFreq_k$ such that $0 <
\TargFreq_i < 1$ for all $i$ and $\TargFreq_1+\cdots+\TargFreq_k \leq 1$.

The problem of estimating the proportion of satisfiable instances of a given
CSP (constraint satisfaction problem) can be tackled through two different
ways: ordering and weighting. Ordering consists in putting a total order on the
domain, which induces an orientation between neighboring solutions in a way
that prevents circuits from appearing, and then counting only minimal elements.
Weighting consists in putting onto each solution a non-negative real value
based on its neighborhood in a way that the total weight is at least 1 for each
satisfiable instance.

The firefighter problem is a monotone dynamic process in graphs that can be
viewed as modeling the use of a limited supply of vaccinations to stop the
spread of an epidemic. In more detail, a fire spreads through a graph, from
burning vertices to their unprotected neighbors. In every round, a small amount
of unburnt vertices can be protected by firefighters. How many firefighters per
turn, on average, are needed to stop the fire from advancing?

An identifying code of a graph G is a dominating set C such that every vertex
x of G is distinguished from all other vertices by the set of vertices in C
that are at distance at most 1 from x. The problem of finding an identifying
code of minimum possible size turned out to be a challenging problem. It was
proved by N. Bertrand that if a graph on n vertices with at least one edge
admits an identifying code, then a minimum identifying code has size at most
n-1.

Given a graph $G$, the longest path problem asks to compute a simple path of
$G$ with the largest number of vertices. This problem is the most natural
optimization version of the well known and well studied Hamiltonian path
problem, and thus it is NP-hard on general graphs. However, in contrast to the
Hamiltonian path problem, there are only few restricted graph families such as
trees and some small graph classes where polynomial algorithms for the longest
path problem have been found.

The study of factoring relations between subshifts or cellular automata is
central in symbolic dynamics. Besides, a notion of intrinsic universality for
cellular automata based on an operation of rescaling is receiving more and more
attention in the literature. In this paper, we propose to study the factoring
relation up to rescalings, and ask for the existence of universal objects for
that simulation relation.

We consider the {\em Capacitated Domination} problem, which models a
service-requirement assignment scenario and is also a generalization of the
well-known {\em Dominating Set} problem. In this problem, given a graph with
three parameters defined on each vertex, namely cost, capacity, and demand, we
want to find an assignment of demands to vertices of least cost such that the
demand of each vertex is satisfied subject to the capacity constraint of each
vertex providing the service.

Breadth First Search (BFS) and other graph traversal techniques are widely
used for measuring large unknown graphs, such as online social networks. It has
been empirically observed that an incomplete BFS is biased toward high degree
nodes. In contrast to more studied sampling techniques, such as random walks,
the precise bias of BFS has not been characterized to date. In this paper, we
quantify the degree bias of BFS sampling.

For an undirected $n$-vertex planar graph $G$ with non-negative edge-weights,
we consider the following type of query: given two vertices $s$ and $t$ in $G$,
what is the weight of a min $st$-cut in $G$? We show how to answer such queries
in constant time with $O(n\log^5n)$ preprocessing time and $O(n\log n)$ space.
We use a Gomory-Hu tree to represent all the pairwise min cuts implicitly.
Previously, no subquadratic time algorithm was known for this problem.

We consider the links between Ramsey theory in the integers, based on van der
Waerden's theorem, and (boolean, CNF) SAT solving. We aim at using the problems
from exact Ramsey theory, concerned with computing Ramsey-type numbers, as a
rich source of test problems, where especially methods for solving hard
problems can be developed.

Optimal (v, 4, 2, 1) optical orthogonal codes (OOC) with $v<=75$ and $v\ne
71$ are classified up to equivalence. One $(v, 4, 2, 1)$ OOC is presented for
all $v\le 181$, for which an optimal OOC exists.

An $r$-graph is an $r$-regular graph where every odd set of vertices is
connected by at least $r$ edges to the rest of the graph. Seymour conjectured
that any $r$-graph is $r+1$-edge-colorable, and also that any $r$-graph
contains $2r$ perfect matchings such that each edge belongs to two of them. We
show that the minimum counter-example to either of these conjectures is a
brick. Furthermore we disprove a variant of a conjecture of Fan, Raspaud.

We consider cubic graphs formed with $k \geq 2$ disjoint claws $C_i \sim
K_{1, 3}$ ($0 \leq i \leq k-1$) such that for every integer $i$ modulo $k$ the
three vertices of degree 1 of $\ C_i$ are joined to the three vertices of
degree 1 of $C_{i-1}$ and joined to the three vertices of degree 1 of
$C_{i+1}$. Denote by $t_i$ the vertex of degree 3 of $C_i$ and by $T$ the set
$\{t_1, t_2,..., t_{k-1}\}$. In such a way we construct three distinct graphs,
namely $FS(1,k)$, $FS(2,k)$ and $FS(3,k)$.

Due to implementation constraints the XOR operation is widely used in order
to combine plaintext and key bit-strings in secret-key block ciphers. This
choice directly induces the classical version of the differential attack by the
use of XOR-kind differences. While very natural, there are many alternatives to
the XOR. Each of them inducing a new form for its corresponding differential
attack (using the appropriate notion of difference) and therefore block-ciphers
need to use S-boxes that are resistant against these nonstandard differential
cryptanalysis.

We introduce a general method to count unlabeled combinatorial structures and
to efficiently generate them at random. The approach is based on pointing
unlabeled structures in an "unbiased" way that a structure of size n gives rise
to n pointed structures. We extend Polya theory to the corresponding pointing
operator, and present a random sampling framework based on both the principles
of Boltzmann sampling and on P\'olya operators. All previously known unlabeled
construction principles for Boltzmann samplers are special cases of our new
results.

Let $a, b$ and $n$ be nonnegative integers $(b \geq a, \ b > 0, \ n \geq 1)$,
$\mathcal{G}_n(a,b)$ be a multigraph on $n$ vertices in which any pair of
vertices is connected with at least $a$ and at most $b$ edges and \textbf{v =}
$(v_1, v_2, ..., v_n)$ be a vector containing $n$ nonnegative integers. We give
a necessary and sufficient condition for the existence of such orientation of
the edges of $\mathcal{G}_n(a,b)$, that the resulted out-degree vector equals
to \textbf{v}. We describe a reconstruction algorithm.

Graceful tree conjecture is a well-known open problem in graph theory. Here
we present a computational approach to this conjecture. An algorithm for
finding graceful labelling for trees is proposed. With this algorithm, we show
that every tree with at most 35 vertices allows a graceful labelling, hence we
verify that the graceful tree conjecture is correct for trees with at most 35
vertices.

The packing chromatic number $\chi_\rho(G)$ of a graph $G$ is the smallest
integer $k$ such that the vertex set $V(G)$ can be partitioned into disjoint
classes $X_1, ..., X_k$, where vertices in $X_i$ have pairwise distance greater
than $i$. For the 2-dimensional square lattice $\mathbb{Z}^2$ it is proved that
$\chi_\rho(\mathbb{Z}^2) \geq 12$, which improves the previously known lower
bound 10.

For $i=2,3$ and a cubic graph $G$ let $\nu_{i}(G)$ denote the maximum number
of edges that can be covered by $i$ matchings. We show that $\nu_{2}(G)\geq
{4/5}| V(G)| $ and $\nu_{3}(G)\geq {7/6}| V(G)| $. Moreover, it turns out that
$\nu_{2}(G)\leq \frac{|V(G)|+2\nu_{3}(G)}{4}$.

Let $#A$ denote the cardinality of a finite set $A$. Let $t(x)=x$ if $x\geq1$
and 1 otherwise. For any two sets $A,B$ denote by $\delta(A,B)$ $=$
$\log_{2}(t(#(B\cap\overline{A})#A))$. We define a new set distance $d(A,B)$
$=$ $\max\{\delta(A,B),\delta(B,A)\} $ motivated by combinatorial notions of
entropy and information \citep{Kolmogorov65}. We prove that $d$ is a
semi-metric on the space of sets of size at least 2. The triangle inequality.
holds for triplets $A$, $B$, $C$ that are not strictly contained one in
another.

We show that the effect of principal pivot transform on the nullity values of
the principal submatrices of a given (square) matrix is described by the
symmetric difference operator (for sets). We consider its consequences for
graphs, and in particular simplify a proof concerning the interlace polynomial.

The basic goal in combinatorial group testing is to identify a set of up to
$d$ defective items within a large population of size $n >> d$ using a pooling
strategy. Namely, the items can be grouped together in pools, and a single
measurement would reveal whether there are one or more defectives in the pool.
The threshold model is a generalization of this idea where a measurement
returns positive if the number of defectives in the pool passes a fixed
threshold $u$, negative if this number is below a fixed lower threshold $\ell
\leq u$, and may behave arbitrarily otherwise.

A partial monoid $P$ is a set with a partial multiplication $\times$ (and
total identity $1_P$) which satisfies some associativity axiom. The partial
monoid $P$ may be embedded in a free monoid $P^*$ and the product $\star$ is
simulated by a string rewriting system on $P^*$ that consists in evaluating the
concatenation of two letters as a product in $P$, when it is defined, and a
letter $1_P$ as the empty word $\epsilon$. In this paper we study the profound
relations between confluence for such a system and associativity of the
multiplication.

We study hierachical segmentation in the framework of edge-weighted graphs.
We define ultrametric watersheds as topological watersheds null on the minima.
We prove that there exists a bijection between the set of ultrametric
watersheds and the set of hierarchical edgesegmentations. We end this paper by
showing how the proposed framework allows to see constrained connectivity as a
classical watershed-based morphological scheme, which provides an efficient
algorithm to compute the whole hierarchy.

We introduce a new approach to model and analyze \emph{Mobility}. It is fully
based on discrete mathematics and yields a class of mobility models, called the
\emph{Markov Trace} Model. This model can be seen as the discrete version of
the \emph{Random Trip} Model including all variants of the \emph{Random
Way-Point} Model \cite{L06}.

A graph $G$ is class II if its chromatic index is at least $\Delta+1$. Let
$H$ be a maximum $\Delta$-colorable subgraph of $G$. We prove best possible
lower bounds for $\frac{|E(H)|}{|E(G)|}$, and structural properties of maximum
$\Delta$-colorable subgraphs. In particular it is shown that every set of
vertex disjoint cycles of a class II graph with $\Delta\geq3$ can be extended
to a maximum $\Delta$-edge colorable subgraph. For simple graphs it is shown
that they have maximum $\Delta$-edge colorable subgraph such that the
complement is a matching.

This paper studies directional dynamics in cellular automata, a formalism
previously introduced by the third author. The central idea is to study the
dynamical behaviour of a cellular automaton through the conjoint action of its
global rule (temporal action) and the shift map (spacial action): qualitative
behaviours inherited from topological dynamics (equicontinuity, sensitivity,
expansivity) are thus considered along arbitrary curves in space-time. The main
contributions of the paper concern equicontinuous dynamics which can be
connected to the notion of consequences of a word.

In this paper we study a new product of graphs called {\em tight product}. A
graph $H$ is said to be a tight product of two (undirected multi) graphs $G_1$
and $G_2$, if $V(H)=V(G_1)\times V(G_2)$ and both projection maps $V(H)\to
V(G_1)$ and $V(H)\to V(G_2)$ are covering maps. It is not a priori clear when
two given graphs have a tight product (in fact, it is $NP$-hard to decide). We
investigate the conditions under which this is possible. This perspective
yields a new characterization of class-1 $(2k+1)$-regular graphs.

Randomized rumor spreading is a classical protocol to disseminate information
across a network. At SODA 2008, a quasirandom version of this protocol was
proposed and competitive bounds for its run-time were proven. This prompts the
question: to what extent does the quasirandom protocol inherit the second
principal advantage of randomized rumor spreading, namely robustness against
transmission failures?

Two Diophantine equation generator function for integer residuals produced by
integer division over closed intervals are presented. One each for the closed
intervals [1,Floor(n^0.5)] and [Ceiling(n^0.5),n], respectively.

An important question arising from the Frobenius Coin Problem is to decide
whether or not a given monetary sum S can be obtained from N coin
denominations. We develop a new Generating Function G(x), where the coefficient
of xi is equal to the number of ways in which coins from the given
denominations can be arranged as a stack whose total monetary worth is i.

The middle levels conjecture asserts that there is a Hamiltonian cycle in the
middle two levels of $2k+1$-dimensional hypercube. The conjecture is known to
be true for $k \leq 17$ [I.Shields, B.J.Shields and C.D.Savage, Disc. Math.,
309, 5271--5277 (2009)]. In this note, we verify that the conjecture is also
true for $k=18$ by constructing a Hamiltonian cycle in the middle two levels of
37-dimensional hypercube with the aid of the computer. We achieve this by
introducing a new decomposition technique and an efficient algorithm for
ordering the Narayana objects.

Choosing a uniformly sampled simple directed graph realization of a degree
sequence has many applications, in particular in social networks where
self-loops are commonly not allowed. It has been shown in the past that one can
perform a Markov chain arc-switching algorithm to sample a simple directed
graph uniformly by performing two types of switches: a 2-switch and a directed
3-cycle reorientation. This paper discusses under what circumstances a directed
3-cycle reorientation is required.

We call a CNF formula linear if any two clauses have at most one variable in
common. We show that there exist unsatisfiable linear k-CNF formulas with at
most 4k^2 4^k clauses, and on the other hand, any linear k-CNF formula with at
most 4^k/(8e^2k^2) clauses is satisfiable. The upper bound uses probabilistic
means, and we have no explicit construction coming even close to it.

The paper introduces a modified version of the classical Coupon Collector's
Problem entailing exchanges and cooperation between multiple players. Results
of the development show that, within a proper Markov framework, the complexity
of the Cooperative Multiplayer Coupon Collectors' Problem can be attacked with
an eye to the modeling of resource harvesting and sharing within the context of
Next Generation Network.

The modular decomposition is a technique that applies but is not restricted
to graphs. The notion of module naturally appears in the proofs of many graph
theoretical theorems. Computing the modular decomposition tree is an important
preprocessing step to solve a large number of combinatorial optimization
problems. Since the first polynomial time algorithm in the early 70's, the
algorithmic of the modular decomposition has known an important development.
This paper survey the ideas and techniques that arose from this line of
research.

Internet is a complex network composed by several networks: the Autonomous
Systems, each one designed to transport information efficiently. Routing
protocols aim to find paths between nodes whenever it is possible (i.e., the
network is not partitioned), or to find paths verifying specific constraints
(e.g., a certain QoS is required). As connectivity is a measure related to both
of them (partitions and selected paths) this work provides a formal lower bound
to it based on core-decomposition, under certain conditions, and low complexity
algorithms to find it.

We consider the problem of finding a spanning tree with maximum number of
leaves (MaxLeaf). A 2-approximation algorithm is known for this problem, and a
3/2-approximation algorithm when restricted to graphs where every vertex has
degree 3 (cubic graphs). MaxLeaf is known to be APX-hard in general, and
NP-hard for cubic graphs. We show that the problem is also APX-hard for cubic
graphs. The APX-hardness of the related problem Minimum Connected Dominating
Set for cubic graphs follows.

In this paper we consider the problem of finding a vector that can be written
as a nonnegative integer linear combination of given 0-1 vectors, the
generators, such that the l_1-distance between this vector and a given target
vector is minimized. We prove that this closest vector problem is NP-hard to
approximate within a O(d) additive error, where d is the dimension of the
ambient vector space. We show that the problem can be approximated within a
O(d^{3/2}) additive error in polynomial time, by rounding an optimal solution
of a natural LP relaxation for the problem.

An edge coloring of a graph $G$ with colors $1,2,..., t$ is called an
interval $t$-coloring if for each $i\in \{1,2,...,t\}$ there is at least one
edge of $G$ colored by $i$, the colors of edges incident to any vertex of $G$
are distinct and form an interval of integers. In 1994 Asratian and Kamalian
proved that if a connected graph $G$ admits an interval $t$-coloring, then
$t\leq (d+1) (\Delta -1) +1$, and if $G$ is also bipartite, then this upper
bound can be improved to $t\leq d(\Delta -1) +1$, where $\Delta$ is the maximum
degree in $G$ and $d$ is the diameter of $G$.

We introduce a new graph polynomial that encodes interesting properties of
graphs, for example, the number of matchings and the number of perfect
matchings. Most importantly, for bipartite graphs the polynomial encodes the
number of independent sets (#BIS).

A $(2,1)$-total labeling of a graph $G$ is an assignment $f$ from the vertex
set $V(G)$ and the edge set $E(G)$ to the set $\{0,1,...,k\}$ of nonnegative
integers such that $|f(x)-f(y)|\ge 2$ if $x$ is a vertex and $y$ is an edge
incident to $x$, and $|f(x)-f(y)|\ge 1$ if $x$ and $y$ are a pair of adjacent
vertices or a pair of adjacent edges, for all $x$ and $y$ in $V(G)\cup E(G)$.
The $(2,1)$-total labeling number $\lambda^T_2(G)$ of a graph $G$ is defined as
the minimum $k$ among all possible assignments. In [D. Chen and W. Wang.
(2,1)-Total labelling of outerplanar graphs. Discr. Appl.

An edge coloring of a graph $G$ with colors $1,2,..., t$ is called an
interval $t$-coloring if for each $i\in \{1,2,...,t\}$ there is at least one
edge of $G$ colored by $i$, the colors of edges incident to any vertex of $G$
are distinct and form an interval of integers. A graph $G$ is interval
colorable, if there is $t\geq 1$, for which $G$ has an interval $t$-coloring.
Let $\mathfrak{N}$ be the set of all interval colorable graphs. In 2004 Kubale
and Giaro showed that if $G,H\in \mathfrak{N}$, then the Cartesian product of
these graphs belongs to $\mathfrak{N}$.

We study the maximal number of triangulations that a planar set of $n$ points
can have, and show that it is at most $30^n$. This new bound is achieved by a
careful optimization of the charging scheme of Sharir and Welzl (2006), which
has led to the previous best upper bound of $43^n$ for the problem.

In this paper, we give a general framework for the Boltzmann generation of
colored objects belonging to combinatorial constructible classes. We propose an
intuitive notion called profiled objects which allows the sampling of
size-colored objects (and also of k-colored objects) although the corresponding
class cannot be described by an analytic ordinary generating function.

In this paper, a structural property of the set of lozenge tilings of a
2n-gon is highlighted. We introduce a simple combinatorial value called
Hamming-distance, which is a lower bound for the flipdistance (i.e. the number
of necessary local transformations involving three lozenges) between two given
tilings. It is here proven that, for n<5, the flip-distance between two tilings
is equal to the Hamming-distance. Conversely, for n>5, We show that there is
some deficient pairs of tilings for which the flip connection needs more flips
than the combinatorial lower bound indicates.

A tree T_uni is m-universal for the class of trees if for every tree T of
size m, T can be obtained from T_uni by successive contractions of edges. We
prove that a m-universal tree for the class of trees has at least mln(m) +
(gamma-1)m + O(1) edges where is the Euler's constant and we build such a tree
with less than mc edges for a fixed constant c = 1.984...

Random instances of constraint satisfaction problems such as k-SAT provide
challenging benchmarks. If there are m constraints over n variables there is
typically a large range of densities r=m/n where solutions are known to exist
with probability close to one due to non-constructive arguments. However, no
algorithms are known to find solutions efficiently with a non-vanishing
probability at even much lower densities. This fact appears to be related to a
phase transition in the set of all solutions.

Any constructive continuous function must have a gradually varied
approximation in compact space. However, the refinement of domain for
$\sigma-$-net might be very small. Keeping the original discretization (square
or triangulation), can we get some interesting properties related to gradual
variation? In this note, we try to prove that many harmonic functions are
gradually varied or near gradually varied; this means that the value of the
center point differs from that of its neighbor at most by 2.

Given a right-angled triangle of squares in a grid whose horizontal and
vertical sides are $n$ squares long, let N(n) denote the maximum number of dots
that can be placed into the cells of the triangle such that each row, each
column, and each diagonal parallel to the long side of the triangle contains at
most one dot. It has been proven that

$N(n) = \lfloor \frac{2n+1}{3} \rfloor$.

In this note, we give a new proof of this result using linear programming
techniques.

Deciding whether an arbitrary graph contains a sun was recently shown to be
NP-complete. We show that whether a building-free graph contains a sun can be
decided in O(min$\{m{n^3}, m^{1.5}n^2\}$) time and, if a sun exists, it can be
found in the same time bound. The class of building-free graphs contains many
interesting classes of perfect graphs such as Meyniel graphs which, in turn,
contains classes such as hhd-free graphs, i-triangulated graphs, and parity
graphs. Moreover, there are imperfect graphs that are building-free.

We investigate the partition LP formulation for Steiner trees and extend the
technique of uncrossing, usually applied to set systems, to families of
partitions. Using this technique we further our understanding of LP relaxations
for the Steiner tree problem. Firstly, we show that basic feasible solutions to
the partition LP formulation have sparse support.

In this paper we propose a deterministic algorithm for approximate counting
the $k$-colourings of a graph. We consider two categories of graphs. The first
one is the sparse random graphs $G_{n,d/n}$, where each edge is chosen
independently with probability $d/n$ and $d$ is fixed. The second one is a
family we call {\em locally $\alpha$-dense graphs} of bounded maximum degree
\Delta.

Cartesian products of graphs have been studied extensively since the 1960s.
They make it possible to decrease the algorithmic complexity of problems by
using the factorization of the product. Hypergraphs were introduced as a
generalization of graphs and the definition of Cartesian products extends
naturally to them. In this paper, we give new properties and algorithms
concerning coloring aspects of Cartesian products of hypergraphs. We also
extend a classical prime factorization algorithm initially designed for graphs
to connected conformal hypergraphs using 2-sections of hypergraphs.

We present a simple iterative strategy for measuring the connection strength
between a pair of vertices in a graph. The method is attractive in that it has
a linear complexity and can be easily parallelized. Based on an analysis of the
convergence property, we propose a mutually reinforcing model to explain the
intuition behind the strategy. The practical effectiveness of this measure is
demonstrated through several combinatorial optimization problems on graphs and
hypergraphs.

We study the interplay between principal pivot transform (pivot) and loop
complementation for graphs. This is done by generalizing loop complementation
(in addition to pivot) to set systems. We show that the operations together,
when restricted to single vertices, form the permutation group S_3. This leads,
e.g., to a normal form for sequences of pivots and loop complementation on
graphs.

A frequently encountered problem in peer review systems is to facilitate
pairwise comparisons of a given set of proposals by as few as referees as
possible. In [8], it was shown that, if each referee is assigned to review k
proposals then ceil{n(n-1)/k(k-1)} referees are necessary and ceil{n(2n-k)/k^2}
referees are sufficient to cover all n(n-1)/2 pairs of n proposals. While the
upper bound remains within a factor of 2 of the lower bound, it becomes
relatively large for small values of k and the ratio of the upper bound to the
lower bound is not less than 3/2 when 2 <= k <= n/2.

We introduce the s-Plex Cluster Vertex Deletion problem. Like the Cluster
Vertex Deletion problem, it is NP-hard and motivated by graph-based data
clustering. While the task in Cluster Vertex Deletion is to delete vertices
from a graph so that its connected components become cliques, the task in
s-Plex Cluster Vertex Deletion is to delete vertices from a graph so that its
connected components become s-plexes. An s-plex is a graph in which every
vertex is nonadjacent to at most s-1 other vertices; a clique is an 1-plex.

We are given a stack of pancakes of different sizes and the only allowed
operation is to take several pancakes from top and flip them. The unburnt
version requires the pancakes to be sorted by their sizes at the end, while in
the burnt version they additionally need to be oriented burnt-side down. We
present an algorithm with the average number of flips, needed to sort a stack
of n burnt pancakes, equal to 7n/4+O(1) and a randomized algorithm for the
unburnt version with at most 17n/12+O(1) flips on average.