Source author record

Shmuel Zaks

Shmuel Zaks appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics Networking and Internet Architecture Computational Complexity Distributed, Parallel, and Cluster Computing math.CO Software Engineering

Catalog footprint

What is connected

8works

7topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Multicast Communications in Tree Networks with Heterogeneous Capacity Constraints

A widely studied problem in communication networks is that of finding the maximum number of communication requests that can be scheduled concurrently, subject to node and/or link capacity constraints. In this paper, we consider the problem of finding the largest number of multicast communication requests that can be serviced simultaneously by a network of tree topology, subject to heterogeneous capacity constraints. This problem generalizes the following two problems studied in the literature: a) the problem of finding a largest induced $k$-colorable subgraph of a chordal graph, b) the maximum multi-commodity flow problem in tree networks. The problem is already known to be NP-hard and to admit a $c$-approximation ($c \approx 1.58$) in the case of homogeneous capacity constraints. We first show that the problem is much harder to approximate in the heterogeneous case. We then use a generalization of a classical algorithm to obtain an $M$-approximation where $M$ is the maximum number of leaves of the subtrees representing the multicast communications. Surprisingly, the same algorithm, though in various disguises, is used in the literature at least four times to solve related problems (though the analysis is different). The special case of the problem where instances are restricted to unicast communications in a star topology network is known to be polynomial-time solvable. We extend this result and show that the problem can be solved in polynomial time for a set of paths in a tree that share a common vertex.

preprint2015arXiv

Designing Low Cost and Energy Efficient Access Network for the Developing World

Internet is growing rapidly in the developing world now. Our survey of four networks in India, all having at least one thousand users, suggest that both installation cost and recurring cost due to power consumption pose a challenge in its deployment in developing countries. In this paper, we first model the access design problem by dividing the users in two types 1) those that may access the network anytime and 2) those who need it only during office hours on working days. The problem is formulated as a binary integer linear program which turns out to be NP-hard. We then give a distributed heuristic for network design. We evaluate our model and heuristic using real data collected from IIT Kanpur LAN for more than 50 days. Results show that even in a tree topology -- which is a common characteristic of all networks who participated in our study, our design can reduce the energy consumption of the network by up to 11% in residential-cum-office environments and up to 22% in office-only environments in comparison with current methods without giving up on the performance. The extra cost incurred due to our design can be compensated in less than an year by saving in electricity bill of the network.

preprint2015arXiv

Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Towards Hole Representations-Part I

Given a tree and a set ${\cal P}$ of non-trivial simple paths on it, $VPT({\cal P})$ is the VPT graph (i.e. the vertex intersection graph) of the paths ${\cal P}$ of the tree $T$, and $EPT({\cal P})$ is the EPT graph (i.e. the edge intersection graph) of ${\cal P}$. These graphs have been extensively studied in the literature. Given two (edge) intersecting paths in a graph, their \emph{split vertices} is the set of vertices having degree at least $3$ in their union. A pair of (edge) intersecting paths is termed \emph{non-splitting} if they do not have split vertices (namely if their union is a path). In this work, motivated by an application in all-optical networks, we define the graph $ENPT({\cal P})$ of edge-intersecting non-splitting paths of a tree, termed the ENPT graph, as the (edge) graph having a vertex for each path in ${\cal P}$, and an edge between every pair of paths that are both edge-intersecting and non-splitting. A graph $G$ is an ENPT graph if there is a tree $T$ and a set of paths ${\cal P}$ of $T$ such that $G=ENPT({\cal P})$, and we say that $<T,{\cal P}>$ is a \emph{representation} of $G$. We first show that cycles, trees and complete graphs are ENPT graphs. Our work follows the lines of Golumbic and Jamison's research in which they defined the EPT graph class, and characterized the representations of chordless cycles (holes). It turns out that ENPT holes have a more complex structure than EPT holes. In our analysis, we assume that the EPT graph corresponding to a representation of an ENPT hole is given. We also introduce three assumptions $(P1)$, $(P2)$, $(P3)$ defined on EPT, ENPT pairs of graphs. In this Part I, using the results of Golumbic and Jamison as building blocks, we characterize (a) EPT, ENPT pairs that satisfy $(P1)$, $(P2)$, $(P3)$, and (b) the unique minimal representation of such pairs.

preprint2013arXiv

Online Regenerator Placement

Connections between nodes in optical networks are realized by lightpaths. Due to the decay of the signal, a regenerator has to be placed on every lightpath after at most $d$ hops, for some given positive integer $d$. A regenerator can serve only one lightpath. The placement of regenerators has become an active area of research during recent years, and various optimization problems have been studied. The first such problem is the Regeneration Location Problem ($\prb$), where the goal is to place the regenerators so as to minimize the total number of nodes containing them. We consider two extreme cases of online $\prb$ regarding the value of $d$ and the number $k$ of regenerators that can be used in any single node. (1) $d$ is arbitrary and $k$ unbounded. In this case a feasible solution always exists. We show an $O(\log \abs{X} \cdot \log d)$-competitive randomized algorithm for any network topology, where $X$ is the set of paths of length $d$. The algorithm can be made deterministic in some cases. We show a deterministic lower bound of $Ω\lb$, where $E$ is the edge set. (2) $d=2$ and $k=1$. In this case there is not necessarily a solution for a given input. We distinguish between feasible inputs (for which there is a solution) and infeasible ones. In the latter case, the objective is to satisfy the maximum number of lightpaths. For a path topology we show a lower bound of $\sqrt{l}/2$ for the competitive ratio (where $l$ is the number of internal nodes of the longest lightpath) on infeasible inputs, and a tight bound of 3 for the competitive ratio on feasible inputs.

preprint2012arXiv

On the Intersection of Tolerance and Cocomparability Graphs

It has been conjectured by Golumbic and Monma in 1984 that the intersection of tolerance and cocomparability graphs coincides with bounded tolerance graphs. The conjecture has been proved under some - rather strong - \emph{structural} assumptions on the input graph; in particular, it has been proved for complements of trees, and later extended to complements of bipartite graphs, and these are the only known results so far. Our main result in this article is that the above conjecture is true for every graph $G$ that admits a tolerance representation with exactly one unbounded vertex; note here that this assumption concerns only the given tolerance \emph{representation} $R$ of $G$, rather than any structural property of $G$. Moreover, our results imply as a corollary that the conjecture of Golumbic, Monma, and Trotter is true for every graph $G=(V,E)$ that has no three independent vertices $a,b,c\in V$ such that $N(a) \subset N(b) \subset N(c)$; this is satisfied in particular when $G$ is the complement of a triangle-free graph (which also implies the above-mentioned correctness for complements of bipartite graphs). Our proofs are constructive, in the sense that, given a tolerance representation $R$ of a graph $G$, we transform $R$ into a bounded tolerance representation $R^{\ast}$ of $G$. Furthermore, we conjecture that any \emph{minimal} tolerance graph $G$ that is not a bounded tolerance graph, has a tolerance representation with exactly one unbounded vertex. Our results imply the non-trivial result that, in order to prove the conjecture of Golumbic, Monma, and Trotter, it suffices to prove our conjecture.

preprint2011arXiv

Opportunistic Information Dissemination in Mobile Ad-hoc Networks: adaptiveness vs. obliviousness and randomization vs. determinism

In this paper the problem of information dissemination in Mobile Ad-hoc Networks (MANET) is studied. The problem is to disseminate a piece of information, initially held by a distinguished source node, to all nodes in a set defined by some predicate. We use a model of MANETs that is well suited for dynamic networks and opportunistic communication. In this model nodes are placed in a plane, in which they can move with bounded speed, and communication between nodes occurs over a collision-prone single channel. In this setup informed and uninformed nodes can be disconnected for some time (bounded by a parameter alpha), but eventually some uninformed node must become neighbor of an informed node and remain so for some time (bounded by a parameter beta). In addition, nodes can start at different times, and they can crash and recover. Under the above framework, we show negative and positive results for different types of randomized protocols, and we put those results in perspective with respect to previous deterministic results.

preprint2010arXiv

The Recognition of Tolerance and Bounded Tolerance Graphs

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This subclass of perfect graphs has been extensively studied, due to both its interesting structure and its numerous applications. Several efficient algorithms for optimization problems that are NP-hard on general graphs have been designed for tolerance graphs. In spite of this, the recognition of tolerance graphs - namely, the problem of deciding whether a given graph is a tolerance graph - as well as the recognition of their main subclass of bounded tolerance graphs, have been the most fundamental open problems on this class of graphs (cf. the book on tolerance graphs \cite{GolTol04}) since their introduction in 1982 \cite{GoMo82}. In this article we prove that both recognition problems are NP-complete, even in the case where the input graph is a trapezoid graph. The presented results are surprising because, on the one hand, most subclasses of perfect graphs admit polynomial recognition algorithms and, on the other hand, bounded tolerance graphs were believed to be efficiently recognizable as they are a natural special case of trapezoid graphs (which can be recognized in polynomial time) and share a very similar structure with them. For our reduction we extend the notion of an \emph{acyclic orientation} of permutation and trapezoid graphs. Our main tool is a new algorithm that uses \emph{vertex splitting} to transform a given trapezoid graph into a permutation graph, while preserving this new acyclic orientation property. This method of vertex splitting is of independent interest; very recently, it has been proved a powerful tool also in the design of efficient recognition algorithms for other classes of graphs \cite{MC-Trapezoid}.

preprint1999arXiv

Computation in an algebra of test selection criteria

One of the key concepts in testing is that of adequate test sets. A test selection criterion decides which test sets are adequate. In this paper, a language schema for specifying a large class of test selection criteria is developed; the schema is based on two operations for building complex criteria from simple ones. Basic algebraic properties of the two operations are derived. In the second part of the paper, a simple language-an instance of the general schema-is studied in detail, with the goal of generating small adequate test sets automatically. It is shown that one version of the problem is intractable, while another is solvable by an efficient algorithm. An implementation of the algorithm is described.