Partition dimension of certain classes of series parallel graphs
16
Citation
19
Reference
10
Related Paper
Citation Trend
Keywords:
Disjoint sets
Modular decomposition
Graph partition
Cograph
Disjoint sets
Cite
Citations (28)
We give a bi-criteria approximation algorithm for the Minimum Nonuniform Partitioning problem, recently introduced by Krauthgamer, Naor, Schwartz and Talwar (2014). In this problem, we are given a graph $G=(V,E)$ on $n$ vertices and $k$ numbers $\rho_1,\dots, \rho_k$. The goal is to partition the graph into $k$ disjoint sets $P_1,\dots, P_k$ satisfying $|P_i|\leq \rho_i n$ so as to minimize the number of edges cut by the partition. Our algorithm has an approximation ratio of $O(\sqrt{\log n \log k})$ for general graphs, and an $O(1)$ approximation for graphs with excluded minors. This is an improvement upon the $O(\log n)$ algorithm of Krauthgamer, Naor, Schwartz and Talwar (2014). Our approximation ratio matches the best known ratio for the Minimum (Uniform) $k$-Partitioning problem. We extend our results to the case of "unrelated weights" and to the case of "unrelated $d$-dimensional weights". In the former case, different vertices may have different weights and the weight of a vertex may depend on the set $P_i$ the vertex is assigned to. In the latter case, each vertex $u$ has a $d$-dimensional weight $r(u,i) = (r_1(u,i), \dots, r_d(u,i))$ if $u$ is assigned to $P_i$. Each set $P_i$ has a $d$-dimensional capacity $c(i) = (c_1(i),\dots, c_d(i))$. The goal is to find a partition such that $\sum_{u\in {P_i}} r(u,i) \leq c(i)$ coordinate-wise.
Disjoint sets
Graph partition
Cite
Citations (0)
The goal of this paper is to find vertex disjoint even cycles in graphs. For this purpose, define a $\theta$-graph to be a pair of vertices $u, v$ with three internally disjoint paths joining $u$ to $v$. Given an independence number $\alpha$ and a fixed integer $k$, the results contained in this paper provide sharp bounds on the order $f(k, \alpha)$ of a graph with independence number $\alpha(G) \leq \alpha$ which contains no $k$ disjoint $\theta$-graphs. Since every $\theta$-graph contains an even cycle, these results provide $k$ disjoint even cycles in graphs of order at least $f(k, \alpha) + 1$. We also discuss the relationship between this problem and a generalized ramsey problem involving sets of graphs.
Disjoint sets
Independence number
Indifference graph
Cograph
Cite
Citations (2)
Disjoint sets
Cite
Citations (3)
A theorem of Tverberg from 1966 asserts that every set $X\subset\mathbb{R}^d$ of $n=T(d,r)=(d+1)(r-1)+1$ points can be partitioned into $r$ pairwise disjoint subsets, whose convex hulls have a point in common. Thus every such partition induces an integer partition of $n$ into $r$ parts (that is, $r$ integers $a_1,\ldots,a_r$ satisfying $n=a_1+\cdots+a_r$), where the parts $a_i$ correspond to the number of points in every subset. In this paper, we prove that for any partition $a_i\le d+1$, $i=1,\ldots,r$, there exists a set $X\subset\mathbb{R}^d$ of $n$ points, such that every Tverberg partition of $X$ induces the same partition on $n$, given by the parts $a_1,\ldots,a_r$.
Disjoint sets
Cardinality (data modeling)
Cite
Citations (1)
Cograph
Disjoint sets
Distance-hereditary graph
Indifference graph
Split graph
Factor-critical graph
Characterization
Block graph
Graph factorization
Disjoint union (topology)
Cite
Citations (6)
Disjoint sets
Tree (set theory)
Cite
Citations (7)
Let G=(V;E) and α(G)≥4 be a simple graph oforder n and k≥2 a positive integer,consider the problem of partitioning G into k vertex-disjoint paths under the neighborhood union condition and obtain the new following results:If |N(x_1)∪N(x_2)|+|N(y_1)∪N(y_2)|≥n-k-1 for every four independent vertices,then G can be partitioned intok vertex-disjoint paths,unless G belongs to an easily recognizable classes of exception graphs.
Disjoint sets
Simple graph
Cite
Citations (0)
Cite
Citations (1)
Abstract We say that a graph family ℱ has the Erdös‐Pósa property if there exists a function f ( k ) such that any graph G contains either k disjoint subgraphs each isomorphic to a member of ℱ, or contains a set S of at most f ( k ) vertices such that G — S contains no graph in ℱ. We derive a general sufficient condition for a family of graphs to have the Erdös‐Pósa property. In particular, for any fixed natural number m the collection of cycles of length divisible by m has the Erdös‐Pósa property. As a by‐product, we obtain a polynomially bounded algorithm for finding a cycle of length divisible by m . On the other hand, we describe a general class of planar graphs H such that a collection of subdivisions of H does not have the Erdös‐Pósa property. In fact, H may even be a tree.
Disjoint sets
Cograph
Cite
Citations (101)