Arrow Research search

Author name cluster

David Peleg

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.

81 papers
2 author rows

Possible papers

81

MFCS Conference 2024 Conference Paper

On Key Parameters Affecting the Realizability of Degree Sequences (Invited Paper)

  • Amotz Bar-Noy
  • Toni Böhnlein
  • David Peleg
  • Yingli Ran
  • Dror Rawitz

Call a sequence d = (d_1, d_2, …, d_n) of positive integers graphic, planaric, outer-planaric, or forestic if it is the degree sequence of some arbitrary, planar, outer-planar, or cycle-free graph G, respectively. The two extreme classes of graphic and forestic sequences were given full characterizations. (The latter has a particularly simple criterion: d is forestic if and only if its volume, ∑ d ≡ ∑_i d_i, satisfies ∑ d ≤ 2n - 2.) In contrast, the problems of fully characterizing planaric and outer-planaric degree sequences are still open. In this paper, we discuss the parameters affecting the realizability of degree sequences by restricted classes of sparse graph, including planar graphs, outerplanar graphs, and some of their subclasses (e. g. , 2-trees and cactus graphs). A key parameter is the volume of the sequence d, namely, ∑ d which is twice the number of edges in the realizing graph. For planar graphs, for example, an obvious consequence of Euler’s theorem is that an n-element sequence d satisfying ∑ d > 4n-6 cannot be planaric. Hence, ∑ d ≤ 4n-6 is a necessary condition for d to be planaric. What about the opposite direction? Is there an upper bound on ∑ d that guarantees that if d is graphic then it is also planaric. Does the answer depend on additional parameters? The same questions apply also to sub-classes of the planar graphs. A concrete example that is illustrated in the technical part of the paper is the class of outer-planaric degree sequences. Denoting the number of 1’s in d by ω₁, we show that for a graphic sequence d, if ω₁ = 0 then d is outer-planaric when ∑ d ≤ 3n-3, and if ω₁ > 0 then d is outer-planaric when ∑ d ≤ 3n-ω₁-2. Conversely, we show that there are graphic sequences that are not outer-planaric with ω₁ = 0 and ∑ d = 3n-2, as well as ones with ω₁ > 0 and ∑ d = 3n-ω₁-1.

Details

MFCS Conference 2024 Conference Paper

Sparse Graphic Degree Sequences Have Planar Realizations

  • Amotz Bar-Noy
  • Toni Böhnlein
  • David Peleg
  • Yingli Ran
  • Dror Rawitz

A sequence d = (d_1, d_2, …, d_n) of positive integers is graphic if it is the degree sequence of some simple graph G, and planaric if it is the degree sequence of some simple planar graph G. It is known that if ∑ d ≤ 2n - 2, then d has a realization by a forest, hence it is trivially planaric. In this paper, we seek bounds on ∑ d that guarantee that if d is graphic then it is also planaric. We show that this holds true when ∑ d ≤ 4n-4-2ω₁, where ω₁ is the number of 1’s in d. Conversely, we show that there are graphic sequences with ∑ d = 4n-2ω₁ that are non-planaric. For the case ω₁ = 0, we show that d is planaric when ∑ d ≤ 4n-4. Conversely, we show that there is a graphic sequence with ∑ d = 4n-2 that is non-planaric. In fact, when ∑ d ≤ 4n-6-2ω₁, d can be realized by a graph with a 2-page book embedding.

Details

MFCS Conference 2022 Conference Paper

Graph Realization of Distance Sets

  • Amotz Bar-Noy
  • David Peleg
  • Mor Perry
  • Dror Rawitz

The Distance Realization problem is defined as follows. Given an n × n matrix D of nonnegative integers, interpreted as inter-vertex distances, find an n-vertex weighted or unweighted graph G realizing D, i. e. , whose inter-vertex distances satisfy dist_G(i, j) = D_{i, j} for every 1 ≤ i < j ≤ n, or decide that no such realizing graph exists. The problem was studied for general weighted and unweighted graphs, as well as for cases where the realizing graph is restricted to a specific family of graphs (e. g. , trees or bipartite graphs). An extension of Distance Realization that was studied in the past is where each entry in the matrix D may contain a range of consecutive permissible values. We refer to this extension as Range Distance Realization (or Range-DR). Restricting each range to at most k values yields the problem k-Range Distance Realization (or k-Range-DR). The current paper introduces a new extension of Distance Realization, in which each entry D_{i, j} of the matrix may contain an arbitrary set of acceptable values for the distance between i and j, for every 1 ≤ i < j ≤ n. We refer to this extension as Set Distance Realization (Set-DR), and to the restricted problem where each entry may contain at most k values as k-Set Distance Realization (or k-Set-DR). We first show that 2-Range-DR is NP-hard for unweighted graphs (implying the same for 2-Set-DR). Next we prove that 2-Set-DR is NP-hard for unweighted and weighted trees. We then explore Set-DR where the realization is restricted to the families of stars, paths, or cycles. For the weighted case, our positive results are that for each of these families there exists a polynomial time algorithm for 2-Set-DR. On the hardness side, we prove that 6-Set-DR is NP-hard for stars and 5-Set-DR is NP-hard for paths and cycles. For the unweighted case, our results are the same, except for the case of unweighted stars, for which k-Set-DR is polynomially solvable for any k.

Details

MFCS Conference 2022 Conference Paper

On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph

  • Amotz Bar-Noy
  • Toni Böhnlein
  • David Peleg
  • Dror Rawitz

We consider the problem of characterizing degree sequences that can be realized by a bipartite graph. If a partition of the sequence into the two sides of the bipartite graph is given as part of the input, then a complete characterization has been established over 60 years ago. However, the general question, in which a partition and a realizing graph need to be determined, is still open. We investigate the role of an important class of special partitions, called High-Low partitions, which separate the degrees of a sequence into two groups, the high degrees and the low degrees. We show that when the High-Low partition exists and satisfies some natural properties, analysing the High-Low partition resolves the bigraphic realization problem. For sequences that are known to be not realizable by a bipartite graph or that are undecided, we provide approximate realizations based on the High-Low partition.

Details

MFCS Conference 2021 Conference Paper

Budgeted Dominating Sets in Uncertain Graphs

  • Keerti Choudhary
  • Avi Cohen
  • N. S. Narayanaswamy
  • David Peleg
  • R. Vijayaragunathan

We study the Budgeted Dominating Set (BDS) problem on uncertain graphs, namely, graphs with a probability distribution p associated with the edges, such that an edge e exists in the graph with probability p(e). The input to the problem consists of a vertex-weighted uncertain graph 𝒢 = (V, E, p, ω) and an integer budget (or solution size) k, and the objective is to compute a vertex set S of size k that maximizes the expected total domination (or total weight) of vertices in the closed neighborhood of S. We refer to the problem as the Probabilistic Budgeted Dominating Set (PBDS) problem. In this article, we present the following results on the complexity of the PBDS problem. 1) We show that the PBDS problem is NP-complete even when restricted to uncertain trees of diameter at most four. This is in sharp contrast with the well-known fact that the BDS problem is solvable in polynomial time in trees. We further show that PBDS is 𝖶[1]-hard for the budget parameter k, and under the Exponential time hypothesis it cannot be solved in n^o(k) time. 2) We show that if one is willing to settle for (1-ε) approximation, then there exists a PTAS for PBDS on trees. Moreover, for the scenario of uniform edge-probabilities, the problem can be solved optimally in polynomial time. 3) We consider the parameterized complexity of the PBDS problem, and show that Uni-PBDS (where all edge probabilities are identical) is 𝖶[1]-hard for the parameter pathwidth. On the other hand, we show that it is FPT in the combined parameters of the budget k and the treewidth. 4) Finally, we extend some of our parameterized results to planar and apex-minor-free graphs. Our first hardness proof (Thm. 1) makes use of the new problem of k-Subset Σ-Π Maximization (k-SPM), which we believe is of independent interest. We prove its NP-hardness by a reduction from the well-known k-SUM problem, presenting a close relationship between the two problems.

Details

IJCAI Conference 2017 Conference Paper

Maintaining Communication in Multi-Robot Tree Coverage

  • Mor Sinay
  • Noa Agmon
  • Oleg Maksimov
  • Sarit Kraus
  • David Peleg

Area coverage is an important task for mobile robots, mainly due to its applicability in many domains, such as search and rescue. In this paper we study the problem of multi-robot coverage, in which the robots must obey a strong communication restriction: they should maintain connectivity between teammates throughout the coverage. We formally describe the Multi-Robot Connected Tree Coverage problem, and an algorithm for covering perfect N-ary trees while adhering to the communication requirement. The algorithm is analyzed theoretically, providing guarantees for coverage time by the notion of speedup factor. We enhance the theoretically-proven solution with a dripping heuristic algorithm, and show in extensive simulations that it significantly decreases the coverage time. The algorithm is then adjusted to general (not necessarily perfect) N-ary trees and additional experiments prove its efficiency. Furthermore, we show the use of our solution in a simulated officebuilding scenario. Finally, we deploy our algorithm on real robots in a real office building setting, showing efficient coverage time in practice.

PDF Details

SODA Conference 2016 Conference Paper

Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach

  • David Peleg
  • Shay Solomon

Approximate matchings in fully dynamic graphs have been intensively studied in recent years. Gupta and Peng [FOCS'13] presented a deterministic algorithm for maintaining fully dynamic (1 + ∊)-approximate maximum cardinality matching (MCM) in general graphs with worst-case update time, for any ∊ > 0, where m denotes the current number of edges in the graph. Despite significant research efforts, this update time barrier remains the state-of-the-art even if amortized time bounds and randomization are allowed or the approximation factor is allowed to increase from 1 + ∊ to 2 – ∊, and even in basic graph families such as planar graphs. This paper presents a simple deterministic algorithm whose performance depends on the density of the graph. Specifically, we maintain fully dynamic (1 + ∊)-approximate MCM with worst-case update time O ( α · ∊ –2 ) for graphs with arboricity 1 bounded by α. The update time bound holds even if the arboricity bound α changes dynamically. Since the arboricity ranges between 1 and, our density-sensitive bound O ( α ·∊ –2 ) naturally generalizes the bound of Gupta and Peng. For the family of bounded arboricity graphs (which includes forests, planar graphs, and graphs excluding a fixed minor), in the regime ∊ = O (1) our update time reduces to a constant. This should be contrasted with the previous best 2-approximation results for bounded arboricity graphs, which achieve either an O (log n ) worst-case bound (Kopelowitz et al, ICALP'14) or an amortized bound (He et al. , ISAAC'14), where n stands for the number of vertices in the graph. En route to this result, we provide local algorithms of independent interest for maintaining fully dynamic approximate matching and vertex cover.

Details

SODA Conference 2016 Conference Paper

Local-on-Average Distributed Tasks

  • Merav Parter
  • David Peleg
  • Shay Solomon

A distributed task is local if its time complexity is (nearly) constant, otherwise it is global. Unfortunately, local tasks are relatively scarce, and most distributed tasks require time at least logarithmic in the network size (and often higher than that). In a dynamic setting, i. e. , when the network undergoes repeated and frequent topological changes, such as vertex and edge insertions and deletions, it is desirable to be able to perform a local update procedure around the modified part of the network, rather than running a static global algorithm from scratch following each change. This paper makes a step towards establishing the hypothesis that many (statically) non-local distributed tasks are local-on-average in the dynamic setting, namely, their amortized time complexity is O (log* n ). Towards establishing the plausibility of this hypothesis, we propose a strategy for transforming static O (polylog( n )) time algorithms into dynamic O (log* n ) amortized time update procedures. We then demonstrate the usefulness of our strategy by applying it to several fundamental problems whose static time complexity is logarithmic, including forest-decomposition, edge-orientation and coloring sparse graphs, and show that their amortized time complexity in the dynamic setting is indeed O (log* n ).

Details

FOCS Conference 2015 Conference Paper

The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication

  • Erez Kantor
  • Zvi Lotker
  • Merav Parter
  • David Peleg

Theoretical study of optimization problems in wireless communication often deals with zero-dimensional tasks. For example, the power control problem requires computing a power assignment guaranteeing that each transmitting station is successfully received at a single receiver point. This paper aims at addressing communication applications that require handling 2-dimensional tasks (e. g. , Guaranteeing successful transmission in entire regions rather than in specific points). A natural approach to such tasks is to discretize the 2-dimensional optimization domain, e. g. , By sampling points within the domain. This approach, however, might incur high time and memory requirements, and moreover, it cannot guarantee exact solutions. Towards this goal, we establish the minimum principle for the SINR function with free-space path loss (i. e. , When the signal decays in proportion to the square of the distance between the transmitter and receiver). We then utilize it as a discretization technique for solving two-dimensional problems in the SINR model. This approach is shown to be useful for handling optimization problems over two dimensions (e. g. , Power control, energy minimization), in providing tight bounds on the number of null-cells in the reception map, and in approximating geometrical and topological properties of the wireless reception map (e. g. , Maximum inscribed sphere). Essentially, the minimum principle allows us to reduce the dimension of the optimization domain without losing anything in the accuracy or quality of the solution. More specifically, when the two dimensional optimization domain is bounded and free from any interfering station, the minimum principle implies that it is sufficient to optimize over the boundary of the domain, as the "hardest" points to be satisfied reside on boundary and not in the interior. We believe that the minimum principle, as well as the interplay between continuous and discrete analysis presented in this paper, may pave the way to future study of algorithmic SINR in higher dimensions.

Details

SODA Conference 2014 Conference Paper

Fault Tolerant Approximate BFS Structures

  • Merav Parter
  • David Peleg

A fault-tolerant structure for a network is required to continue functioning following the failure of some of the network's edges or vertices. This paper addresses the problem of designing a fault-tolerant ( α, β ) approximate BFS structure (or FT-ABFS structure for short), namely, a subgraph H of the network G such that subsequent to the failure of some subset F of edges or vertices, the surviving part of H still contains an approximate BFS spanning tree for (the surviving part of) G, satisfying dist( s, v, H \ F ) ≤ α -dist( s, v, G \ F )+ β for every v ∊ V. We first consider multiplicative ( α, 0) FT-ABFS structures resilient to a failure of a single edge or vertex, and present an algorithm that given an n -vertex unweighted undirected graph G and a source s constructs a (3, 0) FT-ABFS structure rooted at s with at most 3 n edges (improving by an O (log n ) factor on the near-tight result of [3]). Assuming at most f edge failures, for constant integer f > 1, we prove that there exists a (poly-time constructible) (3( f +1), ( f +1) log n ) FT-ABFS structure with O ( fn ) edges. We then consider additive (1, β ) FT-ABFS structures. In contrast to the linear size of ( α, 0) FT-ABFS structures, we show that for every β ∊ [1, O (log n )] there exists an n -vertex graph G with a source s for which any (1, β ) FT-ABFS structure rooted at s has Ω( n 1+∊( β ) ) edges, for some function ∊( β ) ∊ (0, 1). In particular, (1, 3) FT-ABFS structures admit a lower bound of Ω( n 5/4 ) edges. These lower bounds demonstrate an interesting dichotomy between multiplicative and additive spanners; whereas ( α, 0) FT-ABFS structures of size O ( n ) exist (for α ≥ 3), their additive counterparts, (1, β ) FT-ABFS structures, are of super-linear size. Our lower bounds are complemented by an upper bound, showing that there exists a poly-time algorithm that for every n -vertex unweighted undirected graph G and source s constructs a (1, 4) FT-ABFS structure rooted at s with at most O ( n 4/3 ) edges.

Details

FOCS Conference 2011 Conference Paper

Local Distributed Decision

  • Pierre Fraigniaud
  • Amos Korman
  • David Peleg

A central theme in distributed network algorithms concerns understanding and coping with the issue of {\em locality}. Despite considerable progress, research efforts in this direction have not yet resulted in a solid basis in the form of a fundamental computational complexity theory for locality. Inspired by sequential complexity theory, we focus on a complexity theory for \emph{distributed decision problems}. In the context of locality, solving a decision problem requires the processors to independently inspect their local neighborhoods and then collectively decide whether a given global input instance belongs to some specified language. We consider the standard $\cal{LOCAL}$ model of computation and define $LD(t)$ (for {\em local decision}) as the class of decision problems that can be solved in $t$ communication rounds. We first study the intriguing question of whether randomization helps in local distributed computing, and to what extent. Specifically, we define the corresponding randomized class $BPLD(t, p, q)$, containing all languages for which there exists a randomized algorithm that runs in $t$ rounds, accepts correct instances with probability at least $p$ and rejects incorrect ones with probability at least $q$. We show that $p^2+q = 1$ is a threshold for the containment of $LD(t)$ in $BPLD(t, p, q)$. More precisely, we show that there exists a language that does not belong to $LD(t)$ for any $t=o(n)$ but does belong to $BPLD(0, p, q)$ for any $p, q\in (0, 1]$ such that $p^2+q\leq 1$. On the other hand, we show that, restricted to hereditary languages, $BPLD(t, p, q) = LD(O(t))$, for any function $t$ and any $p, q\in (0, 1]$ such that $p^2+q&gt, 1$. In addition, we investigate the impact of non-determinism on local decision, and establish some structural results inspired by classical computational complexity theory. Specifically, we show that non-determinism does help, but that this help is limited, as there exist languages that cannot be decided non-deterministically. Perhaps surprisingly, it turns out that it is the combination of randomization with non-determinism that enables to decide \emph{all} languages \emph{in constant time}. Finally, we introduce the notion of local reduction, and establish some completeness results.

Details

MFCS Conference 2004 Conference Paper

Graph Exploration by a Finite Automaton

  • Pierre Fraigniaud
  • David Ilcinkas
  • Guy Peer
  • Andrzej Pelc
  • David Peleg

Abstract A finite automaton, simply referred to as a robot, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the graph or of its size. Its task is to traverse all the edges of the graph. We first show that, for any K -state robot and any d ≥ 3, there exists a planar graph of maximum degree d with at most K +1 nodes that the robot cannot explore. This bound improves all previous bounds in the literature. More interestingly, we show that, in order to explore all graphs of diameter D and maximum degree d, a robot needs Ω( D log d ) memory bits, even if we restrict the exploration to planar graphs. This latter bound is tight. Indeed, a simple DFS at depth D +1 enables a robot to explore any graph of diameter D and maximum degree d using a memory of size O ( D log d ) bits. We thus prove that the worst case space complexity of graph exploration is Θ( D log d ) bits.

Details

MFCS Conference 2002 Invited Paper

Low Stretch Spanning Trees

  • David Peleg

Abstract The paper provides a brief review of problems and results concerning low stretch and low communication spanning trees for graphs.

Details

STOC Conference 2001 Conference Paper

(1+epsilon, beta)-spanner constructions for general graphs

  • Michael Elkin
  • David Peleg

An (α,Β)-spanner of a graph G is a subgraph H such that d_H(u,w)\le α\cdot d_G(u,w)+Β for every pair of vertices u,w, where d_{G'}(u,w) denotes the distance between two vertices u and v in G'. It is known that every graph G has a polynomially constructible (2κ-1,0)-spanner (a.k.a. multiplicative (2κ-1)-spanner) of size O(n^{1+1/κ}) for every integer κ\ge 1, and a polynomially constructible (1,2)-spanner (a.k.a. additive 2-spanner) of size \tO(n^{3/2}). This paper explores hybrid spanner constructions (involving both multiplicative and additive factors) for general graphs and shows that the multiplicative factor can be made arbitrarily close to 1 while keeping the spanner size arbitrarily close to O(n), at the cost of allowing the additive term to be a sufficiently large constant. More formally, we show that for any constant ε, δ > 0 there exists a constant Β = Β(ε, δ) such that for every n-vertex graph G there is an efficiently constructible (1+ ε, Β)-spanner of size O(n^{1 + δ}). It follows that for any constant ε, δ > 0 there exists a constant Β(ε, δ) such that for any n-vertex graph G = (V,E) there exists an efficiently constructible subgraph (V,H) with O(n^{1 +δ}) edges such that d_H(u,w) \le (1 + ε) d_G(u,w) for every pair of vertices.

Details

MFCS Conference 2000 Conference Paper

Informative Labeling Schemes for Graphs

  • David Peleg

Abstract This paper introduces and studies the notion of informative labeling schemes for arbitrary graphs. Let f(W) be a function on subsets of vertices W. An f labeling scheme labels the vertices of a weighted graph G in such a way that f(W) can be inferred efficiently for any vertex subset W of G by merely inspecting the labels of the vertices of W, without having to use any additional information sources. The paper develops f labeling schemes for some functions f over the class of n -vertex trees, including SepLevel, the separation level of any two vertices in the tree, LCA, the least common ancestor of any two vertices, and Center, the center of any three given vertices in the tree. These schemes use O(log 2 n)-bit labels, which is asymptotically optimal. We then turn to weighted graphs and consider the function Steiner (W), denoting the weight of the Steiner tree spanning the vertices of W in the graph. For n -vertex weighted trees with M-bit edge weights, it is shown that there exists a Steiner labeling scheme using O((M+log n) log n) bit labels, which is asymptotically optimal. In the full paper it is shown that for the class of arbitrary n -vertex graphs with M -bit edge weights, there exists an approximate- Steiner labeling scheme, providing an estimate (up to a logarithmic factor) for Steiner (W) using O((M + logn) log 2 n ) bit labels.

Details

FOCS Conference 1999 Conference Paper

A Near-Tight Lower Bound on the Time Complexity of Distributed MST Construction

  • David Peleg
  • Vitaly Rubinovich

This paper presents a lower bound of /spl Omega/~(D+/spl radic/n) on the time required for the distributed construction of a minimum-weight spanning tree (MST) in n-vertex networks of diameter D=/spl Omega/(log n), in the bounded message model. This establishes the asymptotic near-optimality of existing time-efficient distributed algorithms for the problem, whose complexity is O(D+/spl radic/nlog* n).

Details

FOCS Conference 1995 Conference Paper

Tight Fault Locality (Extended Abstract)

  • Shay Kutten
  • David Peleg

The notion of fault local mending was suggested as a paradigm for designing fault tolerant algorithms that scale to large networks. For such algorithms the complexity of recovering is proportional to the number of faults. We refine this notion by introducing the concept of tight fault locality to deal with problems whose complexity (in the absence of faults) is sublinear in the size of the network. For a function whose complexity on an n-node network is f(n), a tightly fault local algorithm recovers a legal global state in O(f(x)) time when the (unknown) number of faults is x. We illustrate this concept by presenting a general transformation for MIS algorithms to make them fault local. In particular, our transformation yields an O(logx) randomized mending algorithm and a 2/sup /spl radic//spl beta/logx/ deterministic mending algorithm for MIS. Similar results are obtained for other local functions such as a /spl Delta/+1 coloring. We also present the first tight fault local mending algorithm for global functions, using our results for MIS. This improves (by a logarithmic factor) the complexity of a previous fault-local mending algorithm for global functions.

Details

FOCS Conference 1993 Conference Paper

A Sub-Linear Time Distributed Algorithm for Minimum-Weight Spanning Trees (Extended Abstract)

  • Juan A. Garay 0001
  • Shay Kutten
  • David Peleg

This paper considers the question of identifying the parameters governing the behavior of fundamental global network problems. Many papers on distributed network algorithms consider the task of optimizing the running time successful when an O(n) bound is achieved on an n-vertex network. We propose that a more sensitive parameter is the network's diameter Diam. This is demonstrated in the paper by providing a distributed minimum-weight spanning tree algorithm whose time complexity is sub-linear in n, but linear in Diam (specifically, O(Diam+n/sup 0. 614/)). Our result is achieved through the application of graph decomposition and edge elimination techniques that may be of independent interest. >

Details

FOCS Conference 1993 Conference Paper

Near-Linear Cost Sequential and Distribured Constructions of Sparse Neighborhood Covers

  • Baruch Awerbuch
  • Bonnie Berger
  • Lenore Cowen
  • David Peleg

This paper introduces the first near-linear (specifically, O(Elog n+nlog/sup 2/ n)) time algorithm for constructing a sparse neighborhood cover in sequential and distributed environments. This automatically implies analogous improvements (from quadratic to near-linear) to all the results in the literature that rely on network decompositions, both in sequential and distributed domains, including adaptive routing schemes with O/spl tilde/(1) stretch and memory, small edge cuts in planar graphs, sequential algorithms for dynamic approximate shortest paths with O/spl tilde/(E) cost for edge insertion/deletion and O/spl tilde/(1) time to answer shortest-path queries, weight and distance-preserving graph spanners with O/spl tilde/(E) running time and space, and distributed asynchronous "from-scratch" breadth-first-search and network synchronizer constructions with O/spl tilde/(1) message and space overhead (down from O(n)). >

Details

FOCS Conference 1993 Conference Paper

On Choosing a Dense Subgraph (Extended Abstract)

  • Guy Kortsarz
  • David Peleg

This paper concerns the problem of computing the densest k-vertex subgraph of a given graph, namely, the subgraph with the most edges, or with the highest edges-to-vertices ratio. A sequence of approximation algorithms is developed for the problem, with each step yielding a better ratio at the cost of a more complicated solution. The approximation ratio of our final algorithm is O/spl tilde/(n/sup 0. 3885/). We also present a method for converting an approximation algorithm for an unweighted graph problem (from a specific class of maximization problems) into one for the corresponding weighted problem, and apply it to the densest subgraph problem. >

Details

FOCS Conference 1990 Conference Paper

Network Synchronization with Polylogarithmic Overhead

  • Baruch Awerbuch
  • David Peleg

The synchronizer is a simulation methodology for simulating a synchronous network by an asynchronous one, thus enabling the execution of a synchronous algorithm on an asynchronous network. Previously known synchronizers require each processor in the network to participate in each pulse of the synchronization process. The resulting communication overhead depends linearly on the number n of network nodes. A synchronizer with overhead only polylogarithmically dependent on n is introduced. This synchronizer can also be realized with polylog(n) space. The polylog-overhead synchronizer is based on involving only the relevant portions of the network in the synchronization process. >

Details

FOCS Conference 1990 Conference Paper

Sparse Partitions (Extended Abstract)

  • Baruch Awerbuch
  • David Peleg

A collection of clustering and decomposition techniques that make possible the construction of sparse and locality-preserving representations for arbitrary networks is presented. The representation method considered is based on breaking the network G(V, E) into connected regions, or clusters, thus obtaining a cover for the network, i. e. a collection of clusters that covers the entire set of vertices V. Several other graph-theoretic structures that are strongly related to covers are discussed. These include sparse spanners, tree covers of graphs and the concepts of regional matchings and diameter-based separators. All of these structures can be constructed by means of one of the clustering algorithms given, and each has proved a convenient representation for handling certain network applications. >

Details

FOCS Conference 1987 Conference Paper

Achievable Cases in an Asynchronous Environment (Extended Abstract)

  • Hagit Attiya
  • Amotz Bar-Noy
  • Danny Dolev
  • Daphne Koller
  • David Peleg
  • Rüdiger Reischuk

The paper deals with achievability of fault tolerant goals in a completely asynchronous distributed system. Fischer, Lynch, and Paterson [FLP] proved that in such a system "nontrivial agreement" cannot be achieved even in the (possible) presence of a single "benign" fault. In contrast, we exhibit two pairs of goals that are achievable even in the presence of up to t ≪ n/2 faulty processors, contradicting the widely held assumption that no nontrivial goals are attainable in such a system. The first pair deals with renaming processors so as to reduce the size of the initial name space. When only uniqueness is required of the new names, we present a lower bound of n + 1 on the size of the new name space, and a renaming algorithm which establishes an upper bound of n + t. In case the new names are required also to preserve the original order, a tight bound of 2t(n- t + 1) - 1 is obtained. The second pair of goals deals with the multi-slot critical section problem. We present algorithms for controlled access to a critical section. As for the number of slots required, a tight bound of t + 1 is proved in case the slots are identical. In the case of distinct slots the upper bound is 2t + 1.

Details