09-08-2012, 04:02 PM
Graph Algorithms and Applications
Graph Algorithms and Applications.pdf (Size: 214.84 KB / Downloads: 97)
Graphs with Bounded Induced Distance
In this work we introduce graphs with bounded induced distance of order k
(BID(k) for short). In any graph belonging to BID(k), the length of every
induced path between every pair of nodes is at most k times the distance
between the same nodes. In communication networks modeled by these gra-
phs any message can be always delivered through a path whose length is at
most k times the best possible one, even if some nodes fail.
In this work we first provide a characterization of graphs in BID(k) by means
of cycle-chord conditions. After that, we investigate classes with order k ≤ 2.
In this context, we note that the class BID(1) is the well known class of
distance-hereditary graphs, and show that 3/2 is a lower bound for the order
k of graphs that are not distance-hereditary. Then we characterize graphs in
BID(3/2) by means of their minimal forbidden induced subgraphs, and we
also show that graphs in BID(2) have a more complex characterization. We
prove that the recognition problem for the generic class BID(k) is Co-NP-
complete. Finally, we show that the split composition can be used to generate
graphs in BID(k).
This is joint work with Serafino Cicerone.
Independent Tree Spanners: Fault-tolerant Spanning
Trees with Constant Distance Guarantees
For any fixed parameter t ≥ 1, a tree t–spanner of a graph G is a spanning
tree T of G such that the distance between every pair of vertices in T is
at most t times their distance in G. In this talk, we incorporate a concept
of fault-tolerance by examining independent tree t–spanners. Given a root
vertex r, this is a pair of tree t–spanners, such that the two paths from any
vertex to r are edge (resp., internally vertex) disjoint. It is shown that a
pair of independent tree 2–spanners can be found in linear time, whereas the
problem for arbitrary t ≥ 4 is NP–complete.
As a less restrictive concept, we treat tree t–root-spanners, where the distance
constraint is relaxed. Here, we show that the problem of finding an indepen-
dent pair of such subgraphs is NP–complete for all t. As a special case,
we then consider direct tree t–root-spanners. These are tree t–root-spanners
where paths from any vertex to the root have to be detour-free. In the edge
independent case, a pair of these can be found in linear time for all t, whereas
the vertex independent case remains NP–complete.
Mimicking Networks
Frank Wagner
Fachbereich Mathematik und Informatik
Freie Universit¨at Berlin
The idea of this talk is to take a network with a set of k special terminal
vertices and replace it by a simpler network with k terminals, that has the
same flow properties. We show that in general a k-terminal network needs a
network of size at least 2
k (3, 4, 5) we present the optimal mimicking networks (with 3, 5, 6 vertices
resp.). For the class of partial k-trees with l terminals we can show that 22k ·l
vertices are enough, for outerplanar graphs 10 · l is already enough.
The problem came up as a tool to design new flow and cut algorithms. It
seems to be of interest on its own.
This is joint work with Shiva Chaudhuri, K.V. Subramanyam, Klaus Kriegel,
Torsten Thiele, and Christos Zaroliagis.
Graph (and Matroid) Algorithms in Statics: Rigidity
of Regular Grid-Like Structures
Andr´as Recski
Faculty of Electrical Engineering and Information
Technical University of Budapest
1. A k × l square grid is considered as a bar-and-joint framework in the
plane. At least k + l − 1 additional diagonal bars are needed to make
it rigid and the minimum systems are just the spanning trees of a
bipartite graph where the two vertex classes correspond to the rows
and columns, respectively, of the grid and edges indicate diagonals in
their intersections (Bolker and Crapo).
graph by inserting new edges but preserving bipartiteness.
2. If the four corners of the grid are pinned down, only k + l −2 diagonal
bars are needed: the corresponding subgraph must be an asymmetric
2-component forest (ratio of cardinalities of the vertex classes in the
components must be different from k/l), see Bolker and Crapo.
Some 10 years ago we extended this construction to arbitrary vertex-
weighted graphs: If F is an arbitrary field and w : V (G) → F is the
weight function satisfying Pv2V (G) w(v) = 0 then those 2-component fo-
rests are asymmetric where Pw(v) 6= 0 for the individual components.
These forests form the bases of some matroids which were shown to be
elementary strong maps of the cycle matroid of G.
3. On the other hand, if we remove one of the original (horizontal or verti-
cal) bars then k+l diagonal bars will be needed. The good systems were
recently characterized (joint result with Zs. G´asp´ar and N. Radics).
In this talk we use this idea to define two new matroidal families on
graphs where the bases are subgraphs with one more (rather than with
one less, as in Part 2) edge than in the spanning trees. Representability
properties of these matroids and their relations to certain submodular
functions (result of A. Frank) are also presented.
Approximability of Scheduling with Fixed Jobs
In the standard scheduling problem of minimizing the makespan one is given
a set of n independent jobs with processing times pj to be scheduled on m
identical machines in such a way that the latest completion time (the make-
span) is minimized. In modern industrial software it has become standard to
work on a variant of this problem, where some of the jobs are already fixed
in the schedule. The remaining jobs are to be assigned to the machines in
such a way that they do not overlap with fixed jobs. In this talk we present a
polynomial time approximation scheme for the scheduling problem with fixed
jobs for the case that the number m of machines is constant. This result is
essentially best possible, as we also show that, unless P = NP, there exists
no polynomial time approximation scheme in the case when the number of
machines is part of the input and no fully polynomial time approximation
scheme in the constant machine case.
This is joint work with M. Scharbrodt and H. Weisser.