Author name cluster

Ralf Klasing

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

21 papers

2 author rows

I&C Journal 2025 Journal Article

Linear programming of monitoring the links of a fractional weighted network using distance

Wen Li
Yaping Mao
Ralf Klasing

In 2022, Foucaud et al. initiated the study of a new graph-theoretic concept called distance-edge-monitoring number (DEM number for short), in the area of network monitoring. In this paper, we study linear programming for the distance-edge-monitoring problem. For a connected graph G = ( V ( G ), E ( G ) ), let h be a function that assigns to each vertex v ∈ V ( G ) a number in [ 0, 1 ]. For a vertex subset X ⊆ V ( G ), denote h ( X ) = Σ v ∈ X h ( v ). Then, the function h is called a monitoring function of G, if for any edge e in G, the weights of these vertices which monitoring the edge e are at least 1. The fractional distance-edge-monitoring number (FDEM number for short) of G, denoted by dem f ( G ), is given by dem f ( G ) = min ⁡ { H | h is a monitoring function of G }, where H = h ( V ( G ) ). In this paper, we obtain some bounds or exact values for the FDEM number of some specific graphs or networks. Moreover, we study the graphs where the FDEM number equals to the DEM number. Finally, we investigate the FDEM number of some convex polytopes.

Details DOI

I&C Journal 2025 Journal Article

The g-good-neighbor diagnosability of product networks under the PMC model

Zhao Wang
Yaping Mao
Sun-Yuan Hsieh
Ralf Klasing

The concept of neighbor connectivity originated from the assessment of the subversion of espionage networks caused by underground resistance movements, and it has now been applied to measure the disruption of networks caused by cascading failures through neighbors. In this paper, we give two necessary and sufficient conditions of the existence of g-good-neighbor diagnosability. We introduce a new concept called g-good neighbor cut-component number (gc number for short), which has close relation with g-good-neighbor diagnosability. Sharp lower and upper bounds of the gc number of general graphs in terms of the g-good neighbor connectivity have been proposed, which provide a formula to compute the g-good-neighbor diagnosability for general graphs (therefore for Cartesian product graphs). As their applications, we get the exact values or bounds for the gc numbers and g-good-neighbor diagnosability of grid, torus networks and generalized cubes.

Details DOI

MFCS Conference 2024 Conference Paper

Algorithms and Complexity for Path Covers of Temporal DAGs

Dibyayan Chakraborty
Antoine Dailly
Florent Foucaud
Ralf Klasing

A path cover of a digraph is a collection of paths collectively containing its vertex set. A path cover with minimum cardinality for a directed acyclic graph can be found in polynomial time [Fulkerson, AMS'56; Cáceres et al. , SODA'22]. Moreover, Dilworth’s celebrated theorem on chain coverings of partially ordered sets equivalently states that the minimum size of a path cover of a DAG is equal to the maximum size of a set of mutually unreachable vertices. In this paper, we examine how far these classic results can be extended to a dynamic setting. A temporal digraph has an arc set that changes over discrete time-steps; if the underlying digraph is acyclic, then it is a temporal DAG. A temporal path is a directed path in the underlying digraph, such that the time-steps of arcs are strictly increasing along the path. Two temporal paths are temporally disjoint if they do not occupy any vertex at the same time. A temporal path cover is a collection 𝒞 of temporal paths that covers all vertices, and 𝒞 is temporally disjoint if all its temporal paths are pairwise temporally disjoint. We study the computational complexities of the problems of finding a minimum-size temporal (disjoint) path cover (denoted as Temporal Path Cover and Temporally Disjoint Path Cover). On the negative side, we show that both Temporal Path Cover and Temporally Disjoint Path Cover are NP-hard even when the underlying DAG is planar, bipartite, subcubic, and there are only two arc-disjoint time-steps. Moreover, Temporally Disjoint Path Cover remains NP-hard even on temporal oriented trees. We also observe that natural temporal analogues of Dilworth’s theorem on these classes of temporal DAGs do not hold. In contrast, we show that Temporal Path Cover is polynomial-time solvable on temporal oriented trees by a reduction to Clique Cover for (static undirected) weakly chordal graphs (a subclass of perfect graphs for which Clique Cover admits an efficient algorithm). This highlights an interesting algorithmic difference between the two problems. Although it is NP-hard on temporal oriented trees, Temporally Disjoint Path Cover becomes polynomial-time solvable on temporal oriented lines and temporal rooted directed trees. Motivated by the hardness result on trees, we show that, in contrast, Temporal Path Cover admits an XP time algorithm with respect to parameter t_max + tw, where t_max is the maximum time-step and tw is the treewidth of the underlying static undirected graph; moreover, Temporally Disjoint Path Cover admits an FPT algorithm with respect to the same parameterization.

Details

I&C Journal 2024 Journal Article

The number of spanning trees for Sierpiński graphs and data center networks

Xiaojuan Zhang
Gang Yang
Changxiang He
Ralf Klasing
Yaping Mao

The number of spanning trees is an important graph invariant related to different topological and dynamic properties of the graph, such as its reliability, synchronization capability and diffusion properties. In 2007, Chang et al. proposed two conjectures on the number of spanning trees of Sierpiński triangle graphs and its spanning tree entropy. In this paper, we completely confirm these conjectures. For data center networks D k, n, we get the exact formula for k = 1, and upper and lower bounds for k ≥ 2. Our results allow also the calculation of the spanning tree entropy of Sierpiński graphs and data center networks.

Details DOI

TCS Journal 2023 Journal Article

The RED-BLUE SEPARATION problem on graphs

Subhadeep Ranjan Dev
Sanjana Dey
Florent Foucaud
Ralf Klasing
Tuomo Lehtilä

We introduce the Red-Blue Separation problem on graphs, where we are given a graph G = ( V, E ) whose vertices are colored either red or blue, and we want to select a (small) subset S ⊆ V, called red-blue separating set, such that for every red-blue pair of vertices, there is a vertex s ∈ S whose closed neighborhood contains exactly one of the two vertices of the pair. We study the computational complexity of Red-Blue Separation, in which one asks whether a given red-blue colored graph has a red-blue separating set of size at most a given integer. We prove that the problem is NP-complete even for restricted graph classes. We also show that it is always approximable in polynomial time within a factor of 2 ln ⁡ n, where n is the order of the input graph. In contrast, for triangle-free graphs and for graphs of bounded maximum degree, we show that Red-Blue Separation is solvable in polynomial time when the size of the smaller color class is bounded by a constant. However, on general graphs, we show that the problem is W [ 2 ] -hard even when parameterized by the solution size plus the size of the smaller color class. We also consider the problem Max Red-Blue Separation where the coloring of the graph is not part of the input. Here, given an input graph G, we want to determine the smallest integer k such that, for every possible red-blue coloring of G, there is a red-blue separating set of size at most k. We show that Max Red-Blue Separation is NP-hard, even for graphs of bounded maximum degree, but can be approximated in polynomial time within a factor of O ( ln 2 ⁡ n ), where n is the order of the input graph. We derive tight bounds on the cardinality of an optimal solution of Max Red-Blue Separation, showing that it can range from logarithmic in the graph order, up to the order minus one. We also give bounds with respect to related parameters. For trees however, we prove an upper bound of two-thirds the order.

Details DOI

TCS Journal 2022 Journal Article

Hardness and approximation for the star p-Hub Routing Cost Problem in metric graphs

Hao-Ping Yeh
Wei Lu
Li-Hsuan Chen
Ling-Ju Hung
Ralf Klasing
Sun-Yuan Hsieh

Given a metric graph G = ( V, E, w ), a specific vertex c ∈ V, and an integer p, let T be a depth-2 spanning tree of G rooted at c such that c is adjacent to p vertices called hubs and each of the remaining vertices is adjacent to a hub. The Star p -Hub Routing Cost Problem is to find a spanning tree T of G satisfying the conditions stated above such that the sum of distances between all pairs of vertices in T is minimized. In this paper, we prove that the Star p -Hub Routing Cost Problem is NP-hard. A 3-approximation algorithm running in time O ( n 2 ) is given for solving the same problem where n is the number of vertices in the input graph. Moreover, we give an example to show that the analysis of the approximation ratio cannot be better than 2 − ϵ for any ϵ > 0.

Details DOI

TCS Journal 2020 Journal Article

Approximation algorithms for the p-hub center routing problem in parameterized metric graphs

Li-Hsuan Chen
Sun-Yuan Hsieh
Ling-Ju Hung
Ralf Klasing

Let G = ( V, E, w ) be a Δ β -metric graph with a distance function w ( ⋅, ⋅ ) on V such that w ( v, v ) = 0, w ( u, v ) = w ( v, u ), and w ( u, v ) ≤ β ⋅ ( w ( u, x ) + w ( x, v ) ) for all u, v, x ∈ V. Given a positive integer p, let H be a spanning subgraph of G satisfying the conditions that vertices (hubs) in C ⊂ V form a clique of size at most p in H, vertices (non-hubs) in V ∖ C form an independent set in H, and each non-hub v ∈ V ∖ C is adjacent to exactly one hub in C. Define d H ( u, v ) = w ( u, f ( u ) ) + w ( f ( u ), f ( v ) ) + w ( v, f ( v ) ) where f ( u ) and f ( v ) are hubs adjacent to u and v in H respectively. Notice that if u is a hub in H then w ( u, f ( u ) ) = 0. Let r ( H ) = ∑ u, v ∈ V d H ( u, v ) be the routing cost of H. The Single Allocation at most p -Hub Center Routing problem is to find a spanning subgraph H of G such that r ( H ) is minimized. In this paper, we show that the Single Allocation at most p -Hub Center Routing problem is NP-hard in Δ β -metric graphs for any β > 1 / 2. Moreover, we give 2β-approximation algorithms running in time O ( n 2 ) for any β > 1 / 2 where n is the number of vertices in the input graph. Finally, we show that the approximation ratio of our algorithms is at least Ω ( β ), and we examine the structure of any potential o ( β ) -approximation algorithm.

Details DOI

TCS Journal 2020 Journal Article

Beachcombing on strips and islands

Evangelos Bampas
Jurek Czyzowicz
David Ilcinkas
Ralf Klasing

A group of mobile robots (beachcombers) have to search collectively every point of a given domain. At any given moment, each robot can be in walking mode or in searching mode. It is assumed that each robot's maximum allowed searching speed is strictly smaller than its maximum allowed walking speed. A point of the domain is searched if at least one of the robots visits it in searching mode. The Beachcombers' Problem consists in developing efficient schedules (algorithms) for the robots which collectively search all the points of the given domain as fast as possible. We consider searching schedules in the following one-dimensional geometric domains: the cycle of a known circumference L, the finite straight line segment of a known length L, and the semi-infinite line [ 0, + ∞ ). We first consider the online Beachcombers' Problem (i. e. the scenario when the robots do not know in advance the length of the segment to be searched), where the robots are initially collocated at the origin of a semi-infinite line. It is sought to design a schedule A with maximum speed S, defined as S = inf ℓ ⁡ ℓ t A ( ℓ ), where t A ( ℓ ) denotes the time when the search of the segment [ 0, ℓ ] is completed under A. We consider a discrete and a continuous version of the problem, depending on whether the infimum is taken over ℓ ∈ N ⁎ or ℓ ≥ 1. We prove that the LeapFrog algorithm, which was proposed in Czyzowicz et al. (2015) [12], is in fact optimal in the discrete case. This settles in the affirmative a conjecture from that paper. We also show how to extend this result to the more general continuous online setting. For the offline version of the Beachcombers' Problem (i. e. the scenario when the robots know in advance the length of the segment to be searched), we consider the t-source Beachcombers' Problem (i. e. all robots start from a fixed number t ≥ 1 of starting positions) on the cycle and on the finite segment. For the t-source Beachcombers' Problem on the cycle, we show that the structure of the optimal solutions is identical to the structure of the optimal solutions to the 2t-source Beachcombers' Problem on a finite segment. In consequence, by using results from Czyzowicz et al. (2014) [13], we prove that the 1-source Beachcombers' Problem on the cycle is NP-hard, and we derive approximation algorithms for the problem. For the t-source variant of the Beachcombers' Problem on the cycle and on the finite segment, we also derive efficient approximation algorithms. One important contribution of our work is that, in all variants of the offline Beachcombers' Problem that we discuss, we allow the robots to change direction of movement and search points of the domain on both sides of their respective starting positions. This represents a significant generalization compared to the model considered in Czyzowicz et al. (2014) [13], in which each robot had a fixed direction of movement that was specified as part of the solution to the problem. We manage to prove that changes of direction do not help the robots achieve optimality.

Details DOI

TCS Journal 2016 Journal Article

Gathering of robots on anonymous grids and trees without multiplicity detection

Gianlorenzo D'Angelo
Gabriele Di Stefano
Ralf Klasing
Alfredo Navarra

The paper studies the gathering problem on grid and tree networks. A team of robots placed at different nodes of the input graph, has to meet at some node and remain there. Robots operate in Look–Compute–Move cycles; in one cycle, a robot perceives the current configuration in terms of occupied nodes (Look), decides whether to move toward one of its neighbors (Compute), and in the positive case makes the computed move instantaneously (Move). Cycles are performed asynchronously for each robot. The problem has been deeply studied for the case of ring networks. However, the known techniques used on rings cannot be directly extended to grids and trees. Moreover, on rings, another assumption concerning the so-called multiplicity detection capability was required in order to accomplish the gathering task. That is, a robot is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one. In this paper, we provide a full characterization about gatherable configurations for grids and trees. In particular, we show that on these topologies, the multiplicity detection is not required. Very interestingly, sometimes the problem appears trivial, as it is for the case of grids with both odd sides, while sometimes the involved techniques require new insights with respect to the well-studied ring case. Moreover, our results reveal the importance of structures like grids and trees that allow to overcome the multiplicity detection with respect to the ring case.

Details DOI

TCS Journal 2015 Journal Article

Rendezvous of heterogeneous mobile agents in edge-weighted networks

Dariusz Dereniowski
Ralf Klasing
Adrian Kosowski
Łukasz Kuszner

We introduce a variant of the deterministic rendezvous problem for a pair of heterogeneous agents operating in an undirected graph, which differ in the time they require to traverse particular edges of the graph. Each agent knows the complete topology of the graph and the initial positions of both agents. The agent also knows its own traversal times for all of the edges of the graph, but is unaware of the corresponding traversal times for the other agent. The goal of the agents is to meet on an edge or a node of the graph. In this scenario, we study the time required by the agents to meet, compared to the meeting time T OPT in the offline scenario in which the agents have complete knowledge about each others' speed characteristics. When no additional assumptions are made, we show that rendezvous in our model can be achieved after time O ( n T OPT ) in an n-node graph, and that such time is essentially in some cases the best possible. However, we prove that the rendezvous time can be reduced to Θ ( T OPT ) when the agents are allowed to exchange Θ ( n ) bits of information at the start of the rendezvous process. We then show that under some natural assumption about the traversal times of edges, the hardness of the heterogeneous rendezvous problem can be substantially decreased, both in terms of time required for rendezvous without communication, and the communication complexity of achieving rendezvous in time Θ ( T OPT ).

Details DOI

TCS Journal 2012 Journal Article

More efficient periodic traversal in anonymous undirected graphs

Jurek Czyzowicz
Stefan Dobrev
Leszek Gąsieniec
David Ilcinkas
Jesper Jansson
Ralf Klasing
Ioannis Lignos
Russell Martin

We consider the problem of periodic graph exploration in which a mobile entity with constant memory, an agent, has to visit all n nodes of an input simple, connected, undirected graph in a periodic manner. Graphs are assumed to be anonymous, that is, nodes are unlabeled. While visiting a node, the agent may distinguish between the edges incident to it; for each node v, the endpoints of the edges incident to v are uniquely identified by different integer labels called port numbers. We are interested in algorithms for assigning the port numbers together with traversal algorithms for agents using these port numbers to obtain short traversal periods. Periodic graph exploration is unsolvable if the port numbers are set arbitrarily; see Budach (1978) [1]. However, surprisingly small periods can be achieved by carefully assigning the port numbers. Dobrev et al. (2005) [4] described an algorithm for assigning port numbers and an oblivious agent (i. e. , an agent with no memory) using it, such that the agent explores any graph with n nodes within the period 10 n. When the agent has access to a constant number of memory bits, the optimal length of the period was proved in Gąsieniec et al. (2008) [7] to be no more than 3. 75 n − 2 (using a different assignment of the port numbers and a different traversal algorithm). In this paper, we improve both these bounds. More precisely, we show how to achieve a period length of at most ( 4 + 1 3 ) n − 4 for oblivious agents and a period length of at most 3. 5 n − 2 for agents with constant memory. To obtain our results, we introduce a new, fast graph decomposition technique called a three-layer partition that may also be useful for solving other graph problems in the future. Finally, we present the first non-trivial lower bound, 2. 8 n − 2, on the period length for the oblivious case.

Details DOI

TCS Journal 2010 Journal Article

Locating and repairing faults in a network with mobile agents

Colin Cooper
Ralf Klasing
Tomasz Radzik

We consider a fixed, undirected, known network and a number of “mobile agents” which can traverse the network in synchronised steps. Some nodes in the network may be faulty and the agents are to find the faults and repair them. The agents could be software agents, if the underlying network represents a computer network, or robots, if the underlying network represents some potentially hazardous physical terrain. Assuming that the first agent encountering a faulty node can immediately repair it, it is easy to see that the number of steps necessary and sufficient to complete this task is Θ ( n / k + D ), where n is the number of nodes in the network, D is the diameter of the network, and k is the number of agents. We consider the case where one agent can repair only one faulty node. After repairing the fault, the agent dies. We show that a simple deterministic algorithm for this problem terminates within O ( n / k + D log f / log log f ) steps, where f = min { n / k, n / D }, assuming that the number of faulty nodes is at most k / 2. We also demonstrate the worst-case asymptotic optimality of this algorithm by showing a network such that for any deterministic algorithm, there is a placement of k / 2 faults forcing the algorithm to work for Ω ( n / k + D log f / log log f ) steps.

Details DOI

TCS Journal 2010 Journal Article

Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring

Ralf Klasing
Adrian Kosowski
Alfredo Navarra

One of the recently considered models of robot-based computing makes use of identical, memoryless mobile units placed in nodes of an anonymous graph. The robots operate in Look–Compute–Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), takes a decision whether to stay idle or to move to one of the nodes adjacent to its current position (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each robot. In such a restricted scenario, we study the influence of symmetries of the robot configuration on the feasibility of certain computational tasks. More precisely, we deal with the problem of gathering all robots at one node of the graph, and propose a solution based on a symmetry-preserving strategy. When the considered graph is an undirected ring and the number of robots is sufficiently large (more than 18), such an approach is proved to solve the problem for all starting situations, as long as gathering is feasible. In this way we also close the open problem of characterizing symmetric situations on the ring which admit a gathering [R. Klasing, E. Markou, A. Pelc: Gathering asynchronous oblivious mobile robots in a ring, Theoret. Comput. Sci. 390 (1) (2008) 27–39]. The proposed symmetry-preserving approach, which is complementary to symmetry-breaking techniques found in related work, appears to be new and may have further applications in robot-based computing.

Details DOI

TCS Journal 2008 Journal Article

A randomized algorithm for the joining protocol in dynamic distributed networks

Colin Cooper
Ralf Klasing
Tomasz Radzik

We describe a randomized algorithm for assigning neighbours to vertices joining a dynamic distributed network. The aim of the algorithm is to maintain connectivity, low diameter and constant vertex degree. On joining each vertex donates a constant number of tokens to the network. These tokens contain the address of the donor vertex. The tokens make independent random walks in the network. A token can be used by any vertex it is visiting to establish a connection to the donor vertex. This allows joining vertices to be allocated a random set of neighbours although the overall vertex membership of the network is unknown. The network we obtain in this way is robust under adversarial deletion of vertices and edges and actively reconnects itself. One model we consider is a network constructed in this fashion, in which vertices join but never leave. If t is the size of the network, then the diameter of the network is O ( log t ) for all t, with high probability. As an example of the robustness of this model, suppose an adversary deletes edges from the network leaving components of size at least t 1 / 2 + δ. With high probability the network reconnects itself by replacing lost edges using tokens from the token pool.

Details DOI

TCS Journal 2008 Journal Article

Gathering asynchronous oblivious mobile robots in a ring

Ralf Klasing
Euripides Markou
Andrzej Pelc

We consider the problem of gathering identical, memoryless, mobile robots in one node of an anonymous unoriented ring. Robots start from different nodes of the ring. They operate in Look–Compute–Move cycles and have to end up in the same node. In one cycle, a robot takes a snapshot of the current configuration (Look), makes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each robot. For an odd number of robots we prove that gathering is feasible if and only if the initial configuration is not periodic, and we provide a gathering algorithm for any such configuration. For an even number of robots we decide the feasibility of gathering except for one type of symmetric initial configurations, and provide gathering algorithms for initial configurations proved to be gatherable.

Details DOI

TCS Journal 2008 Journal Article

On the complexity of bandwidth allocation in radio networks

Ralf Klasing
Nelson Morales
Stéphane Pérennes

We define and study an optimization problem that is motivated by bandwidth allocation in radio networks. Because radio transmissions are subject to interference constraints in radio networks, physical space is a common resource that the nodes have to share in such a way, that concurrent transmissions do not interfere. The bandwidth allocation problem we study under these constraints is the following. Given bandwidth (traffic) demands between the nodes of the network, the objective is to schedule the radio transmissions in such a way that the traffic demands are satisfied. The problem is similar to a multicommodity flow problem, where the capacity constraints are replaced by the more complex notion of non-interfering transmissions. We provide a formal specification of the problem that we call round weighting. By modeling non-interfering radio transmissions as independent sets, we relate the complexity of round weighting to the complexity of various independent set problems (e. g. maximum weight independent set, vertex coloring, fractional coloring). From this relation, we deduce that in general, round weighting is hard to approximate within n 1 − ε ( n being the size of the radio network). We also provide polynomial (exact or approximation) algorithms e. g. in the following two cases: (a) when the interference constraints are specific (for instance for a network whose vertices belong to the Euclidean space), or (b) when the traffic demands are directed towards a unique node in the network (also called gathering, analogous to single commodity flow).

Details DOI

TCS Journal 2007 Journal Article

Hardness and approximation results for Black Hole Search in arbitrary networks

Ralf Klasing
Euripides Markou
Tomasz Radzik
Fabiano Sarracco

A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. The Black Hole Search is the task of locating all black holes in a network by exploring it with mobile agents. We consider the problem of designing the fastest Black Hole Search, given the map of the network and the starting node. We study the version of this problem that assumes that there is at most one black hole in the network and there are two agents, which move in synchronized steps. We prove that this problem is NP-hard in arbitrary graphs (even in planar graphs), solving an open problem stated in [J. Czyzowicz, D. Kowalski, E. Markou, A. Pelc, Searching for a black hole in tree networks, in: Proc. 8th Int. Conf. on Principles of Distributed Systems, OPODIS 2004, 2004, pp. 34–35. Also: Springer LNCS, vol. 3544, pp. 67–80]. We also give a 3 3 8 -approximation algorithm, showing the first non-trivial approximation ratio upper bound for this problem. Our algorithm follows a natural approach of exploring networks via spanning trees. We prove that this approach cannot lead to an approximation ratio bound better than 3/2.

Details DOI

TCS Journal 2004 Journal Article

On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality

Hans-Joachim Böckenhauer
Dirk Bongartz
Juraj Hromkovič
Ralf Klasing
Guido Proietti
Sebastian Seibert
Walter Unger

In this paper we investigate the problem of finding a 2-connected spanning subgraph of minimal cost in a complete and weighted graph G. This problem is known to be APX-hard, for both the edge and the vertex connectivity case. Here we prove that the APX-hardness still holds even if one restricts the edge costs to an interval [ 1, 1 + ε ], for an arbitrary small ε > 0. This result implies the first explicit lower bound on the approximability of the general version (i. e. , for arbitrary graphs) of the problem. On the other hand, if the input graph satisfies the sharpened β -triangle inequality, then a 2 3 + 1 3 · β 1 - β -approximation algorithm is designed. This ratio tends to 1 with β tending to 1 2, and it improves the previous known bound of 3 2, holding for graphs satisfying the triangle inequality, as soon as β < 5 7. Furthermore, a generalized problem of increasing to 2 the edge-connectivity of any spanning subgraph of G by means of a set of edges of minimum cost is considered. This problem is known to admit a 2-approximation algorithm. Here we show that whenever the input graph satisfies the sharpened β -triangle inequality with β < 2 3, then this ratio can be improved to β 1 - β.

Details DOI

TCS Journal 2002 Journal Article

Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem

Hans-Joachim Böckenhauer
Juraj Hromkovič
Ralf Klasing
Sebastian Seibert
Walter Unger

The investigation of the possibility to efficiently compute approximations of hard optimization problems is one of the central and most fruitful areas of current algorithm and complexity theory. The aim of this paper is twofold. First, we introduce the notion of stability of approximation algorithms. This notion is shown to be of practical as well as of theoretical importance, especially for the real understanding of the applicability of approximation algorithms and for the determination of the border between easy instances and hard instances of optimization problems that do not admit polynomial-time approximation. Secondly, we apply our concept to the study of the traveling salesman problem (TSP). We show how to modify the Christofides algorithm for Δ-TSP to obtain efficient approximation algorithms with constant approximation ratio for every instance of TSP that violates the triangle inequality by a multiplicative constant factor. This improves the result of Andreae and Bandelt (SIAM J. Discrete Math. 8 (1995) 1).

Details DOI

I&C Journal 1997 Journal Article

Optimal Algorithms for Broadcast and Gossip in the Edge-Disjoint Path Modes

Juraj Hromkovič
Ralf Klasing
Walter Unger
Hubert Wagener

The communication power of the one-way and two-way edge-disjoint path modes for broadcast and gossip is investigated. The complexity of communication algorithms is measured by the number of communication steps (rounds). The main results achieved are the following: 1. For each connected graphGn ofnnodes, the complexity of broadcast inGn, B min(Gn ), satisfies ⌈log2 n⌉⩽B min(Gn )⩽⌈log2 n⌉+1. The complete binary trees meet the upper bound, and all graphs containing a Hamiltonian path meet the lower bound. 2. For each connected graphGn ofnnodes, the one-way (two-way) gossip complexityR(Gn ) (R 2(Gn )) satisfies⌈log2 n⌉⩽R2(Gn)⩽2·⌈log2 n⌉+1, 1. 44. .. log2 n⩽R(Gn)⩽2·⌈log2 n⌉+2. All these lower and upper bounds are shown to be sharp up to 1. 3. All planar graphs ofnnodes and degreehhave a two-way gossip complexity of at least 1. 5log2 n−log2 log2 n−0. 5log2 h−8, and the two-dimensional grid ofnnodes has the gossip complexity 1. 5log2 n−log2 log2 n±O(1); i. e. , two-dimensional grids are optimal gossip structures among planar graphs of bounded degree. Some upper bounds are also obtained for the one-way mode. 4. Thed-dimensional grid, d⩾3, ofnnodes has the two-way gossip complexity (1+1/d)·log2 n−log2 n log2 n±O(d).

Details DOI

MFCS Conference 1994 Conference Paper

The Relationship Between Gossiping in Vertex-Disjoint Paths Mode and Bisection Width

Ralf Klasing

Abstract The two-way communication mode used for sending messages to processors of interconnection networks via vertex-disjoint paths in one communication step is investigated. The complexity of communication algorithms is measured by the number of communication steps (rounds). This paper establishes a direct relationship between the gossip complexity and the vertex bisection width. More precisely, the main results are the following: 1. The lower bound 2 log 2 n − log 2 k − log 2 log 2 k − 2 is proved on the number of rounds of every two-way gossip algorithm working on any graph G n, k of n nodes and vertex bisection k. 2. A graph G n, k of n nodes and vertex bisection k, and a two-way gossip algorithm for G n, k is constructed working in 2 log 2 n − log 2 k −log 2 log 2 k + 2 rounds. The first result improves the lower bound of 2 log 2 n −log 2 k −log 2 log 2 n −2 from [J. Hromkovič, R. Klasing, E. A. Stöhr, H. Wagener, ”Gossiping in Vertex-Disjoint Paths Mode in d-Dimensional Grids and Planar Graphs”, Proc. of the First Annual European Symposium on Algorithms (ESA '93), Springer LNCS 726, pp. 200–211]. The second result shows that this improvement is the best possible with respect to the class of all graphs G n, k of n nodes and vertex bisection k.

Details