EDITORS' CHOICE 2003
All abstracts are free to view on Science Direct.
DISCRETE MATHEMATICS – EDITORS' CHOICE 2003
Association schemes and permutation groups
| |
|
|
Every permutation group which is not
2-transitive acts on a non-trivial coherent configuration, but the
question of which permutation groups G act on non-trivial association
schemes (symmetric coherent configurations) is considerably more subtle. A
closely related question is: when is there a unique minimal G-invariant association scheme? We
examine these questions, and relate them to more familiar concepts of
permutation group theory (such as generous transitivity) and association
scheme theory (such as stratifiability). Our main results are the
determination of all regular groups having a unique minimal association
scheme, and a classification of groups with no non-trivial association
scheme. The latter must be primitive, and are 2-homogeneous, or almost
simple, or of diagonal type. The diagonal groups have some very
interesting features, and we examine them further. Among other things we
show that a diagonal group with non-abelian base group cannot be
stratifiable if it has ten or more factors, or generously transitive if it
has nine or more; and we characterise the quaternion group Q8 as the unique
non-abelian group T such that a
diagonal group with eight factors T is generously
transitive |
Thresholds for families of multisets, with an
application to graph pebbling | |
|
|
In this paper we prove two multiset analogs of classical results. We prove a multiset analog of Lovász's version of the Kruskal–Katona Theorem and an analog of the Bollobás–Thomason threshold result. As a corollary we obtain the existence of pebbling thresholds for arbitrary graph sequences. In addition, we improve both the lower and upper bounds for the ‘random pebbling’ threshold of the sequence of paths. |
A root graph that is locally the line graph of
the Petersen graph • ARTICLE | |
|
|
We construct a root graph on 192 vertices
that is locally the line graph of the Petersen graph, a new
distance-regular graph on 96 vertices (with intersection array
{15,10,1;1,2,15} and automorphism group 24.Sym(6)), and several new
strongly regular graphs (with parameters (v,k, |
,
)=(96,20,4,4)
and (96,19,2,4)) and square 2-(96,20,4)
designs.
Relaxed game chromatic number of
graphs • ARTICLE | |
|
|
This paper discusses a coloring game on
graphs. Let k,d be non-negative integers and C a set of k colors. Two persons, Alice and
Bob, alternately color the vertices of G with colors from C, with Alice having the first
move. A color i is legal for an
uncolored vertex x if by
coloring x with color i, the subgraph of G induced by those vertices of
color i has maximum degree at
most d. Each move of Alice or
Bob colors an uncolored vertex with a legal color. The game is over if
either all vertices are colored, or no more vertices can be colored with a
legal color. Alice's goal is to produce a legal coloring which colors all
the vertices of G, and Bob's
goal is to prevent this from happening. We shall prove that if G is a forest, then for k=3,d |
1, Alice has a winning strategy. If
G is an outerplanar graph, then
for k=6 and d
Anti-Lecture Hall Compositions •
SHORT
COMMUNICATION
| ||||
|
|
We study the set Ak of integer sequences
and show that the generating function is
where |
To our knowledge this is a new result that complements
the family of the Lecture | |||
Extremal weight enumerators and ultraspherical
polynomials • ARTICLE
| |
|
|
We establish an upper bound for the minimum distance of a divisible code in terms of its dual distance. The bound generalizes the Mallows–Sloane bounds for self-dual codes. We obtain a linear recurrence for the distance distribution components of codes that attain the bound. From this we derive known conditions for the existence of extremal self-dual codes in a much simpler way. In the second half of the paper, we determine zeta functions for the codes that attain our new bound. Zeta functions for linear codes are defined in Duursma (Trans. Amer. Math. Soc. 351(9) (1999) 3609). Using properties of ultraspherical polynomials, we show that the zeta function of a quaternary extremal self-dual code has its zeros on the circle |T|=q−1/2 in analogy with the zeta function of an algebraic curve. |
Maximal arcs in Steiner systems S(2,4,v) •
ARTICLE | |
|
|
A maximal arc in a Steiner system S(2,4,v) is a set of elements which intersects every block in either two or zero elements. It is well known that v≡4 (mod 12) is a necessary condition for an S(2,4,v) to possess a maximal arc. We describe methods of constructing an S(2,4,v) with a maximal arc, and settle the longstanding sufficiency question in a strong way. We show that for any v≡4 (mod 12), we can construct a resolvable S(2,4,v) containing a triple of maximal arcs, all mutually intersecting in a common point. An application to the motivating colouring problem is presented. |
On graph closures •
ARTICLE
| |
|
|
Ryjá |
ek
(J. Combin. Theory B 70 (1997) 217) introduced a very useful notion of a
closure cl(G) for a claw-free
graph G and proved, in
particular, that c(G)=c(cl(G)) where c(H) is the length of a longest
cycle in H. In this paper, we
describe some strengthenings of the main results in Ryjá
(G) that can be used in a wider
class of graphs, and show, in particular, that c(G)=c(
A universal bound for a covering in regular
posets and its application to pool testing •
ARTICLE | |||
|
|
Let V(n) be the set of all 2n subsets of the set Nn={1,2,…,n} and Vi(n)={x
with the first inequality as an equality if and only if
C is a Steiner S(i,{k,k+1},n) design with a specified
distance distribution. A generalization of this result to the case of
monotone left-regular n-posets
is given. One of motivating applications is the problem of reconstructing
an unknown binary vector x of length
n using pool testing under the
condition that the vectors x are
distributed with probabilities p|x|(1−p)n−|x| where x
This improves upon an information theoretic bound for
the minimum average number E(n,p) of tests to reconstruct an
unknown x using
two-stage pool testing and allows determination of the asymptotic behavior
of E(n,p) up to a positive constant
factor as n→ | ||
V(n): |x|=i}. For a fixed i=1,…,n, consider a covering operator F:Vi(n)→V(n) such that x
F(x) for any x
,
consider the decreasing continuous function gi(T)=k+((k+1)/i)(1−
)
where k and
,
and 1−i/(k+1)<
1. Using averaging and linear
programing it is proved that 
under
some restrictions upon p=p
On the measures of pseudorandomness of binary
sequences • ARTICLE | |
|
|
In several earlier papers the authors
studied finite pseudorandom binary sequences EN |
A bijection between nonnegative words and sparse
abba-free
partitions • SHORT
COMMUNICATION
| |
|
|
We construct a bijection proving that the following two sets have the same cardinality: (i) the set of words over {−1,0,1} of length m−2 which have every initial sum nonnegative, and (ii) the set of partitions of {1,2,…,m} such that no two consecutive numbers lie in the same block and for no four numbers the middle two are in one block and the end two are in another block. The words were considered by Gouyou-Beauchamps and Viennot who enumerated by means of them certain animals. The identity connecting (i) and (ii) was observed by Klazar who proved it by generating functions. |
me
On the number of Hamiltonian cycles in Dirac
graphs • ARTICLE | |
|
|
In response to a question of Bondy, bounds are established on the minimum number of Hamiltonian cycles in all graphs of order n and minimum degree at least n/2. |
DISCRETE APPLIED MATHEMATICS – EDITORS' CHOICE 2003
On easy and hard hereditary classes of graphs
with respect to the independent set problem •
ARTICLE
| |
|
|
In this paper we introduce the concept of a boundary class, which is a helpful tool for classification of hereditary classes of graphs according to the complexity of the independent set problem. It is shown that in a class X defined by a finite set of forbidden induced subgraphs, the problem is NP-hard if and only if X includes a boundary class. The paper presents a particular boundary class and establishes several new polynomially solvable cases for the independent set problem. |
The power of small coalitions in
graphs • ARTICLE | |
|
|
This paper considers the question of the
influence of a coalition of vertices, seeking to gain control (or
majority) in local neighborhoods in a general graph. Say that a vertex v is controlled by the coalition M if the majority of its neighbors
are from M. We ask how many
vertices (as a function of |M|)
can M control in this fashion.
Upper and lower bounds are provided for this problem, as well as for cases
where the majority is computed over larger neighborhoods (either
neighborhoods of some fixed radius r |
Local search algorithms for the k-cardinality tree
problem • ARTICLE
| |
|
|
In this paper we deal with an |
-hard
combinatorial optimization problem, the k-cardinality tree problem in
node-weighted graphs. This problem has several applications, which justify
the need for efficient methods to obtain good solutions. We review
existing literature on the problem. Then we prove that under the condition
that the graph contains exactly one trough, the problem can be solved in
polynomial time. For the general
Discrete facility location and routing of
obnoxious activities •
ARTICLE | |
|
|
The problem of simultaneously locating
obnoxious facilities and routing obnoxious materials between a set of
built-up areas and the facilities is addressed. Obnoxious facilities are those facilities which cause exposure to people as well as to the environment i.e. dump sites, chemical industrial plants, electric power supplier networks, nuclear reactors and so on. A discrete combined location-routing model, which we refer to as Obnoxious Facility Location and Routing model (OFLR), is defined. OFLR is a NP-hard problem for which a Lagrangean heuristic approach is presented. The Lagrangean relaxation proposed allows to decompose OFLR into a Location subproblem and a Routing subproblem; such subproblems are then strengthened by adding suitable inequalities. Based on this Lagrangean relaxation two simple Lagrangean heuristics are provided. An effective Branch and Bound algorithm is then presented, which aims at reducing the gap between the above mentioned lower and upper bounds. Our Branch and Bound exploits the information gathered while going down in the enumeration tree in order to solve efficiently the subproblems related to other nodes. This is accomplished by using a bundle method to solve at each node the Lagrangean dual. Some variants of the proposed Branch and Bound method are defined in order to identify the best strategy for different classes of instances. A comparison of computational results relative to these variants is presented. |
Finding a central vertex in an HHD-free
graph • ARTICLE | |
|
|
In a graph G=(V,E), the eccentricity e(v) of a vertex v is max{d(v,u): u |
Query efficient implementation of graphs of
bounded clique-width •
ARTICLE | |
|
|
If P(x1,…,xk) is a graph property
expressible in monadic second-order
logic, where x1,…,xk denote vertices, if
G is a graph with n vertices and of clique-width at
most p where p is fixed, then we can associate
with each vertex u of G a piece of information I(u) of size O(log(n)) such that, for all vertices x1,…,xk of G, one can decide whether P(x1,…,xk) holds in time
O(log(n)) by using only I(x1),…,I(xk). The preprocessing
can be done in time O(n log(n)). One can do the same for any fixed monadic second-order optimization
function (like distance) by using information of size O(log2(n)) for each vertex and
computation time O(log2(n)). In
this case preprocessing time is O(–log2(n)). Clique-width is a complexity measure on graphs similar to
tree-width, but more powerful since every set of graphs of bounded
tree-width has bounded clique-width, but not conversely.
Similar results apply to graphs of tree-width at most w and to properties and functions expressed in the version of monadic second-order logic allowing quantifications on sets of edges. |
Which matrices are immune against the
transportation paradox? •
SHORT
COMMUNICATION | |
|
|
We characterize the m×n cost matrices of the
transportation problem for which there exist supplies and demands such
that the transportation paradox arises. Our characterization is fairly
simple and can be verified within O(mn) computational steps. Moreover,
we discuss the corresponding question for the algebraic transportation
problem |
neko,
Bettina Klinz and Gerhard J. Woeginger
The base-matroid and inverse combinatorial
optimization problems •
ARTICLE | |
|
|
A new matroid is introduced: this matroid is defined starting from any matroid and one of its bases, hence we call it base-matroid. Besides some properties of the base-matroid, a non-trivial algorithm for the solution of the related matroid optimization problem is presented. The new matroid has application in the field of inverse combinatorial optimization problems. We discuss in detail the LP formulation of the inverse matroid optimization problem and we propose an efficient algorithm for computing its primal and dual solutions. |
A push-relabel framework for submodular function
minimization and applications to parametric optimization •
ARTICLE
| |
|
|
Recently, the first combinatorial strongly polynomial algorithms for submodular function minimization have been devised independently by Iwata, Fleischer, and Fujishige and by Schrijver. In this paper, we improve the running time of Schrijver's algorithm by designing a push-relabel framework for submodular function minimization (SFM). We also extend this algorithm to carry out parametric minimization for a strong map sequence of submodular functions in the same asymptotic running time as a single SFM. Applications include an efficient algorithm for finding a lexicographically optimal base. |
Restricted t-matchings in bipartite
graphs • ARTICLE | |
|
|
Given a simple bipartite graph G and an integer t |
Combined connectivity augmentation and
orientation problems •
ARTICLE | |
|
|
Two important branches of graph connectivity problems are connectivity augmentation, which consists of augmenting a graph by adding new edges so as to meet a specified target connectivity, and connectivity orientation, where the goal is to find an orientation of an undirected or mixed graph that satisfies some specified edge-connection property. In the present work, an attempt is made to link the above two branches, by considering degree-specified and minimum cardinality augmentation of graphs so that the resulting graph admits an orientation satisfying a prescribed edge-connection requirement, such as (k,l)-edge-connectivity. The results are obtained by combining the supermodular polyhedral methods used in connectivity orientation with the splitting off operation, which is a standard tool in solving augmentation problems. |
On the orientation of graphs and
hypergraphs • ARTICLE | |
|
|
Graph orientation is a well-studied area of combinatorial optimization, one that provides a link between directed and undirected graphs. An important class of questions that arise in this area concerns orientations with connectivity requirements. In this paper we focus on how similar questions can be asked about hypergraphs, and we show that often the answers are also similar: many known graph orientation theorems can be extended to hypergraphs, using the familiar uncrossing techniques. Our results also include a short proof and an extension of a theorem of Khanna et al. (Proceedings of the Eleventh Annual ACM–SIAM Symposium on Discrete Alogrithm, 2001, pp. 663–671), and a new orientation theorem that provides a characterization for (2k+1)-edge-connected graphs. |
A greedy algorithm for convex
geometries • ARTICLE | |
|
|
Convex geometries are closure spaces which satisfy anti-exchange property, and they are known as dual of antimatroids. We consider functions defined on the sets of the extreme points of a convex geometry. Faigle–Kern (Math. Programming 72 (1996) 195–206) presented a greedy algorithm to linear programming problems for shellings of posets, and Krüger (Discrete Appl. Math. 99 (2002) 125–148) introduced b-submodular functions and proved that Faigle–Kern's algorithm works for shellings of posets if and only if the given set function is b-submodular. We extend their results to all classes of convex geometries, that is, we prove that the same algorithm works for all convex geometries if and only if the given set function on the extreme sets is submodular in our sense. |
Efficient dualization of O(log n)-term monotone disjunctive
normal forms • SHORT
COMMUNICATION
| |
|
|
This paper shows that O(log n)-term monotone disjunctive
normal forms (DNFs) |
can
be dualized in incremental polynomial time, where n is the number of variables in
Heuristics and meta-heuristics for 2-layer
straight line crossing minimization •
ARTICLE | |
|
|
This paper presents extensive computational experiments to compare 12 heuristics and 2 meta-heuristics for the problem of minimizing straight-line crossings in a 2-layer graph. These experiments show that the performance of the heuristics (largely based on simple ordering rules) drastically deteriorates as the graphs become sparser. A tabu search metaheuristic yields the best results for relatively dense graphs, with a GRASP implementation as close second. Furthermore, the GRASP approach outperforms all other approaches when tackling low-density graphs. |
New characterizations of M-convex functions and
their applications to economic equilibrium models with
indivisibilities • ARTICLE | |
|
|
The concept of M-convex functions plays a
central role in "discrete convex analysis", a unified framework of
discrete optimization recently developed by Murota and others. This paper
gives two new characterizations of M- and M |
-convex functions generalizing Gul
and Stacchetti's results on the equivalence among the single improvement
condition, the gross substitutes condition and the no complementarities
condition for set functions (utility functions on {0,1} vectors) as well
as Fujishige and Yang's observation on the connection to M-convexity. We
also discuss implications of our results in an exchange economy with
indivisible goods.
Bidirected and unidirected capacity installation
in telecommunication networks •
ARTICLE | |
|
|
In the design of telecommunication
networks, decisions concerning capacity installation and routing of
commodities have to be taken simultaneously. Network Loading problems
formalize these decisions in mathematical optimization models. Several
variants of the problem exist: bifurcated or non-bifurcated routing,
bidirected or unidirected capacity installation, and symmetric versus
non-symmetric routing restrictions. Moreover, different concepts of
reliability can be considered. In this paper, we study the polyhedral
structure of two basic problems for non-bifurcated routing: network
loading with bidirected and unidirected capacity installation.
We show that strong valid inequalities for the substructure restricted to a single edge, are also strong valid inequalities for the overall models. In a computational study, several classes of inequalities, both for the substructure and the overall problem, are compared on real-life instances for both variants of network loading. |
A primal–dual approximation algorithm for the
survivable network design problem in hypergraphs ARTICLE
| |
|
|
Given a hypergraph with nonnegative costs
on hyperedges, and a weakly supermodular function r : 2V→Z+, where V is the vertex set, we consider
the problem of finding a minimum cost subset of hyperedges such that for
every set S |
,
where dmax+ is the
maximum degree of hyperedges of positive costs, rmax=maxS r(S), and
.
In particular, our result contains a
-approximation
algorithm for ECP, which gives an independent and complete proof for the
result first obtained by Jain et al. (Proceedings of the SODA, 1999, p.
484–489