EDITORS' CHOICE 2003
All abstracts are free to view on Science Direct.
DISCRETE MATHEMATICS | DISCRETE
APPLIED MATHEMATICS
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