### Refine

#### Document Type

- ZIB-Report (2)
- In Proceedings (1)
- Master's Thesis (1)

#### Is part of the Bibliography

- no (4)

#### Keywords

- line planning (1)
- unimodal demand (1)

#### Institute

We consider the problem of partitioning a weighted graph into k
connected components of similar weight. In particular, we consider the two classical objectives to maximize the lightest part or to minimize the heaviest part. For a partitioning of the vertex set and for both objectives, we give the first known approximation results on general graphs. Specifically, we give a $\Delta$-approximation where $\Delta$ is the maximum degree of an arbitrary spanning tree of the given graph.
Concerning the edge partition case, we even obtain a 2-approximation for the min-max and the max-min problem, by using the claw-freeness of line graphs.

Bus rapid transit systems in developing and newly
industrialized countries often consist of a trunk with a path
topology. On this trunk, several overlapping lines are operated
which provide direct connections. The demand varies heavily over the
day, with morning and afternoon peaks typically in reverse
directions. We propose an integer programming
model for this problem, derive a structural property of line plans
in the static (or single period) ``unimodal demand'' case, and
consider approaches to the solution of the multi-period version that
rely on clustering the demand into peak and off-peak service
periods. An application to the Metrobüs system of Istanbul is
discussed.