BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Mordechai Shalom

Mordechai Shalom 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 AlgorithmsComputational ComplexityDiscrete Mathematicsmath.CONetworking and Internet Architecture

Catalog footprint

What is connected

8works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

8 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the Maximum Cardinality Cut Problem in Proper Interval Graphs and Related Graph Classes

Although it has been claimed in two different papers that the maximum cardinality cut problem is polynomial-time solvable for proper interval graphs, both of them turned out to be erroneous. In this paper, we give FPT algorithms for the maximum cardinality cut problem in classes of graphs containing proper interval graphs and mixed unit interval graphs when parameterized by some new parameters that we introduce. These new parameters are related to a generalization of the so-called bubble representations of proper interval graphs and mixed unit interval graphs and to clique-width decompositions.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Edge Coloring with Minimum Reload/Changeover Costs

In an edge-colored graph, a traversal cost occurs at a vertex along a path when consecutive edges with different colors are traversed. The value of the traversal cost depends only on the colors of the traversed edges. This concept leads to two global cost measures, namely the \emph{reload cost} and the \emph{changeover cost}, that have been studied in the literature and have various applications in telecommunications, transportation networks, and energy distribution networks. Previous work focused on problems with an edge-colored graph being part of the input. In this paper, we formulate and focus on two pairs of problems that aim to find an edge coloring of a graph so as to minimize the reload and changeover costs. The first pair of problems aims to find a proper edge coloring so that the reload/changeover cost of a set of paths is minimized. The second pair of problems aim to find a proper edge coloring and a spanning tree so that the reload/changeover cost is minimized. We present several hardness results as well as polynomial-time solvable special cases.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On two extensions of equimatchable graphs

A graph is said to be equimatchable if all its maximal matchings are of the same size. In this work we introduce two extensions of the property of equimatchability by defining two new graph parameters that measure how far a graph is from being equimatchable. The first one, called the matching gap, measures the difference between the sizes of a maximum matching and a minimum maximal matching. The second extension is obtained by introducing the concept of equimatchable sets; a set of vertices in a graph $G$ is said to be equimatchable if all maximal matchings of $G$ saturating the set are of the same size. Noting that $G$ is equimatchable if and only if the empty set is equimatchable, we study the equimatchability defect of the graph, defined as the minimum size of an equimatchable set in it. We develop several inapproximability and parameterized complexity results and algorithms regarding the computation of these two parameters, a characterization of graphs of unit matching gap, exact values of the equimatchability defect of cycles, and sharp bounds for both parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Parameterized complexity of the MINCCA problem on graphs of bounded decomposability

In an edge-colored graph, the cost incurred at a vertex on a path when two incident edges with different colors are traversed is called reload or changeover cost. The "Minimum Changeover Cost Arborescence" (MINCCA) problem consists in finding an arborescence with a given root vertex such that the total changeover cost of the internal vertices is minimized. It has been recently proved by Gözüpek et al. [TCS 2016] that the problem is FPT when parameterized by the treewidth and the maximum degree of the input graph. In this article we present the following results for the MINCCA problem: - the problem is W[1]-hard parameterized by the treedepth of the input graph, even on graphs of average degree at most 8. In particular, it is W[1]-hard parameterized by the treewidth of the input graph, which answers the main open problem of Gözüpek et al. [TCS 2016]; - it is W[1]-hard on multigraphs parameterized by the tree-cutwidth of the input multigraph; - it is FPT parameterized by the star tree-cutwidth of the input graph, which is a slightly restricted version of tree-cutwidth. This result strictly generalizes the FPT result given in Gözüpek et al. [TCS 2016]; - it remains NP-hard on planar graphs even when restricted to instances with at most 6 colors and 0/1 symmetric costs, or when restricted to instances with at most 8 colors, maximum degree bounded by 4, and 0/1 symmetric costs.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Maximum Cut Problem in Co-bipartite Chain Graphs

A \emph{co-bipartite chain} graph is a co-bipartite graph in which the neighborhoods of the vertices in each clique can be linearly ordered with respect to inclusion. It is known that the maximum cut problem (MaxCut) is NP-Hard in co-bipartite graphs. We consider MaxCut in co-bipartite chain graphs. We first consider the twin-free case and present an explicit solution. We then show that MaxCut is polynomial time solvable in this graph class.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access