TY - GEN A1 - Krumke, Sven A1 - Marathe, Madhav A1 - Poensgen, Diana A1 - Ravi, Sekharipuram S. A1 - Wirth, Hans-Christoph T1 - Budgeted Maximal Graph Coverage N2 - An instance of the \emph{maximum coverage} problem is given by a set of weighted ground elements and a cost weighted family of subsets of the ground element set. The goal is to select a subfamily of total cost of at most that of a given budget maximizing the weight of the covered elements. We formulate the problem on graphs: In this situation the set of ground elements is specified by the nodes of a graph, while the family of covering sets is restricted to connected subgraphs. We show that on general graphs the problem is polynomial time solvable if restricted to sets of size at most~$2$, but becomes NP-hard if sets of size~$3$ are permitted. On trees, we prove polynomial time solvability if each node appears in a fixed number of sets. In contrast, if vertices are allowed to appear an unbounded number of times, the problem is NP-hard even on stars. We finally give polynomial time algorithms for special cases where the subgraphs form paths and the host graph is a line, a cycle or a star. T3 - ZIB-Report - 02-24 KW - budgeted maximum coverage KW - approximation algorithm KW - dynamic programming Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6918 ER - TY - GEN A1 - Hauptmeier, Dietrich A1 - Krumke, Sven A1 - Rambau, Jörg A1 - Wirth., Hans-Christoph T1 - Euler is Standing in Line N2 - In this paper we study algorithms for ``Dial-a-Ride'' transportation problems. In the basic version of the problem we are given transportation jobs between the vertices of a graph and the goal is to find a shortest transportation that serves all the jobs. This problem is known to be NP-hard even on trees. We consider the extension when precedence relations between the jobs with the same source are given. Our results include a polynomial time algorithm on paths and an approximation algorithm on general graphs with a performance of~$9/4$. For trees we improve the performance to~$5/3$. T3 - ZIB-Report - SC-99-06 KW - NP-completeness KW - polynomial-time approximation algorithms KW - stacker-crane problem KW - vehicle routing KW - elevator system KW - Eulerian Cycle Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3947 ER - TY - GEN A1 - Krumke, Sven A1 - Noltemeier, Hartmut A1 - Wirth, Hans-Christoph T1 - Graphentheoretische Konzepte und Algorithmen N2 - Das vorliegende Skript bietet eine Einf{ü}hrung in die Graphentheorie und graphentheoretische Algorithmen. Im zweiten Kapitel werden Grundbegriffe der Graphentheorie vorgestellt. Das dritte Kapitel besch{ä}ftigt sich mit der Existenz von Wegen in Graphen. Hier wird auch die L{ö}suung des ber{ü}hmten K{ö}nigsberger Br{ü}ckenproblems aufgezeigt und der Satz von Euler bewiesen. Im vierten Kapitel wird gezeigt, wie man auf einfache Weise die Zusammenhangskomponenten eines Graphen bestimmen kann. Im Kapitel sechs wird dann sp{ä}ter mit der Tiefensuche ein Verfahren vorgestellt, das schneller arbeitet und mit dessen Hilfe man noch mehr Informationen {ü}ber die Struktur eines Graphen gewinnen kann. In den folgenden Kapiteln werden Algorithmen vorgestellt, um minimale aufspannenden B{ä}ume, k{ü}rzeste Wege und maximale Fl{ü}sse in Graphen zu bestimmen. Am Ende des Skripts wird ein kurzer Einblick in die planaren Graphen und Graphhomomorphismen geboten. T3 - ZIB-Report - 00-19 KW - Graphen KW - Algorithmen KW - Komplexit{ä}t KW - kombinatorische Optimierung Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5873 ER -