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 the Seidel complementation on ($P_5, \bar{P_5}, Bull)$-free
graphs

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 propose a novel distributed algorithm to decompose graphs or cluster data.
The algorithm recovers the solution obtained from spectral clustering without
need for expensive eigenvalue/ eigenvector computations. We demonstrate that by
solving the wave equation on the graph, every node can assign itself to a
cluster by performing a local fast Fourier transform. We prove the equivalence
of our algorithm to spectral clustering, derive convergence rates and
demonstrate it on examples.

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.

The Unreactive Markovian Evader Interdiction Problem (UME) asks to optimally
place sensors on a network to detect Markovian motion by one or more "evaders".
It was previously proved that finding the optimal sensor placement is NP-hard
if the number of evaders is unbounded. Here we show that the problem is NP-hard
with just 2 evaders using a connection to coloring of planar graphs. The
results suggest that approximation algorithms are needed even in applications
where the number of evaders is small.

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.

Tilings and tiling systems are an abstract concept that arise both as a
computational model and as a dynamical system. In this paper, we characterize
the sets of periods that a tiling system can produce. We prove that up to a
slight recoding, they correspond exactly to languages in the complexity classes
$\nspace{n}$ and $\cne$.

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.