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

Ramin Javadi

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

ResearcherUnclaimed source record
math.COComputational ComplexityComputer VisionDiscrete Mathematics

Catalog footprint

What is connected

8works
4topics
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)

preprint2022arXiv

The Game of Cops and Robber on (Claw, Even-hole)-free Graphs

In this paper, we study the game of cops and robber on the class of graphs with no even hole (induced cycle of even length) and claw (a star with three leaves). The cop number of a graph $G$ is defined as the minimum number of cops needed to capture the robber. Here, we prove that the cop number of all claw-free even-hole-free graphs is at most two and, in addition, the capture time is at most $2n$ rounds, where $n$ is the number of vertices of the graph. Moreover, our results can be viewed as a first step towards studying the structure of claw-free even-hole-free graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Decompositions of complete uniform multi-hypergraphs into Berge paths and cycles of arbitrary lengths

In 1981, Alspach conjectured that the complete graph $ K_{n} $ could be decomposed into cycles of arbitrary lengths, provided that the obvious necessary conditions would hold. This conjecture was proved completely by Bryant, Horsley and Pettersson in 2014. Moreover, in 1983, Tarsi conjectured that the obvious necessary conditions for packing pairwise edge-disjoint paths of arbitrary lengths in the complete multigraphs were also sufficient. The conjecture was confirmed by Bryant in 2010. In this paper, we investigate an analogous problem as the decomposition of the complete uniform multi-hypergraph $ μK_{n}^{(k)} $ into Berge cycles and Berge paths of arbitrary given lengths. We show that for every integer $ μ\geq 1 $, $ n\geq 108 $ and $ 3\leq k<n $, $ μK_{n}^{(k)} $ can be decomposed into Berge cycles and Berge paths of arbitrary lengths, provided that the obvious necessary conditions hold, thereby generalizing a result by Kühn and Osthus on the decomposition of $K_{n}^{(k)}$ into Hamilton Berge cycles. Furthermore, we obtain the necessary and sufficient conditions for packing the cycles of arbitrary lengths in the complete multigraphs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On The Isoperimetric Spectrum of Graphs and Its Approximations

In this paper we consider higher isoperimetric numbers of a (finite directed) graph. In this regard we focus on the $n$th mean isoperimetric constant of a directed graph as the minimum of the mean outgoing normalized flows from a given set of $n$ disjoint subsets of the vertex set of the graph. We show that the second mean isoperimetric constant in this general setting, coincides with (the mean version of) the classical Cheeger constant of the graph, while for the rest of the spectrum we show that there is a fundamental difference between the $n$th isoperimetric constant and the number obtained by taking the minimum over all $n$-partitions. In this direction, we show that our definition is the correct one in the sense that it satisfies a Federer-Fleming-type theorem, and we also define and present examples for the concept of a supergeometric graph as a graph whose mean isoperimetric constants are attained on partitions at all levels. Moreover, considering the ${\bf NP}$-completeness of the isoperimetric problem on graphs, we address ourselves to the approximation problem where we prove general spectral inequalities that give rise to a general Cheeger-type inequality as well. On the other hand, we also consider some algorithmic aspects of the problem where we show connections to orthogonal representations of graphs and following J.~Malik and J.~Shi ($2000$) we study the close relationships to the well-known $k$-means algorithm and normalized cuts method.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Pairwise Balanced Designs and Sigma Clique Partitions

In this paper, we are interested in minimizing the sum of block sizes in a pairwise balanced design, where there are some constraints on the size of one block or the size of the largest block. For every positive integers n;m, where m ? n, let S(n;m) be the smallest integer s for which there exists a PBD on n points whose largest block has size m and the sum of its block sizes is equal to s. Also, let S0(n;m) be the smallest integers for which there exists a PBD on n points which has a block of size m and the sum of it block sizes is equal to s. We prove some lower bounds for S(n;m) and S0(n;m). Moreover, we apply these bounds to determine the asymptotic behaviour of the sigma clique partition number of the graph Kn-Km, Cocktail party graphs and complement of paths and cycles.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Clustering Using Isoperimetric Number of Trees

In this paper we propose a graph-based data clustering algorithm which is based on exact clustering of a minimum spanning tree in terms of a minimum isoperimetry criteria. We show that our basic clustering algorithm runs in $O(n \log n)$ and with post-processing in $O(n^2)$ (worst case) time where $n$ is the size of the data set. We also show that our generalized graph model which also allows the use of potentials at vertices can be used to extract a more detailed pack of information as the {\it outlier profile} of the data set. In this direction we show that our approach can be used to define the concept of an outlier-set in a precise way and we propose approximation algorithms for finding such sets. We also provide a comparative performance analysis of our algorithm with other related ones and we show that the new clustering algorithm (without the outlier extraction procedure) behaves quite effectively even on hard benchmarks and handmade examples.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Local Clique Covering of Graphs

A k-clique covering of a simple graph G, is an edge covering of G by its cliques such that each vertex is contained in at most k cliques. The smallest k for which G admits a k-clique covering is called local clique cover number of G and is denoted by $lcc(G)$. Local clique cover number can be viewed as the local counterpart of the clique cover number which is equal to the minimum total number of cliques covering all edges. In this paper, several aspects of the problem are studied and its relationships to other well-known problems are discussed. Moreover, the local clique cover number of claw-free graphs and its subclasses are notably investigated. In particular, it is proved that local clique cover number of every claw-free graph is at most $cΔ/ \logΔ$, where $Δ$ is the maximum degree of the graph and $c$ is a universal constant. It is also shown that the bound is tight, up to a constant factor. Furthermore, it is established that local clique number of the linear interval graphs is bounded by $\logΔ+ 1/2 \log \logΔ+ O(1)$. Finally, as a by-product, a new Bollobas-type inequality is obtained for the intersecting pairs of set systems.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On Complexity of Isoperimetric Problems on Trees

This paper is aimed to investigate some computational aspects of different isoperimetric problems on weighted trees. In this regard, we consider different connectivity parameters called {\it minimum normalized cuts}/{\it isoperimteric numbers} defined through taking minimum of the maximum or the mean of the normalized outgoing flows from a set of subdomains of vertices, where these subdomains constitute a {\it partition}/{\it subpartition}. Following the main result of [A. Daneshgar, {\it et. al.}, {\it On the isoperimetric spectrum of graphs and its approximations}, JCTB, (2010)], it is known that the isoperimetric number and the minimum normalized cut both can be described as $\{0,1\}$-optimization programs, where the latter one does {\it not} admit a relaxation to the reals. We show that the decision problem for the case of taking $k$-partitions and the maximum (called the max normalized cut problem {\rm NCP}$^M$) as well as the other two decision problems for the mean version (referred to as {\rm IPP}$^m$ and {\rm NCP}$^m$) are $NP$-complete problems. On the other hand, we show that the decision problem for the case of taking $k$-subpartitions and the maximum (called the max isoperimetric problem {\rm IPP}$^M$) can be solved in {\it linear time} for any weighted tree and any $k \geq 2$. Based on this fact, we provide polynomial time $O(k)$-approximation algorithms for all different versions of $k$th isoperimetric numbers considered. Moreover, when the number of partitions/subpartitions, $k$, is a fixed constant, as an extension of a result of B. Mohar (1989) for the case $k=2$ (usually referred to as the Cheeger constant), we prove that max and mean isoperimetric numbers of weighted trees as well as their max normalized cut can be computed in polynomial time. We also prove some hardness results for the case of simple unweighted graphs and trees.

0 citations0 reviewsNo code linkedOpen access