Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Steiner distance problem for large vertex subsets in the hypercube
47
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We find the asymptotic behavior of the Steiner k-diameter of the $n$-cube if $k$ is large. Our main contribution is the lower bound, which utilizes the probabilistic method.
rate research
Read More
In this short note we consider the oriented vertex Turan problem in the hypercube: for a fixed oriented graph $overrightarrow{F}$, determine the maximum size $ex_v(overrightarrow{F}, overrightarrow{Q_n})$ of a subset $U$ of the vertices of the oriented hypercube $overrightarrow{Q_n}$ such that the induced subgraph $overrightarrow{Q_n}[U]$ does not contain any copy of $overrightarrow{F}$. We obtain the exact value of $ex_v(overrightarrow{P_k}, overrightarrow{Q_n})$ for the directed path $overrightarrow{P_k}$, the exact value of $ex_v(overrightarrow{V_2}, overrightarrow{Q_n})$ for the directed cherry $overrightarrow{V_2}$ and the asymptotic value of $ex_v(overrightarrow{T}, overrightarrow{Q_n})$ for any directed tree $overrightarrow{T}$.
For a connected graph $G:=(V,E)$, the Steiner distance $d_G(X)$ among a set of vertices $X$ is the minimum size among all the connected subgraphs of $G$ whose vertex set contains $X$. The $k-$Steiner distance matrix $D_k(G)$ of $G$ is a matrix whose rows and columns are indexed by $k-$subsets of $V$. For $k$-subsets $X_1$ and $X_2$, the $(X_1,X_2)-$entry of $D_k(G)$ is $d_G(X_1 cup X_2)$. In this paper, we show that the rank of $2-$Steiner distance matrix of a caterpillar graph on $N$ vertices and with $p$ pendant veritices is $2N-p-1$.
Given a graph $G = (V,E)$ and a subset $T subseteq V$ of terminals, a emph{Steiner tree} of $G$ is a tree that spans $T$. In the vertex-weighted Steiner tree (VST) problem, each vertex is assigned a non-negative weight, and the goal is to compute a minimum weight Steiner tree of $G$. We study a natural generalization of the VST problem motivated by multi-level graph construction, the emph{vertex-weighted grade-of-service Steiner tree problem} (V-GSST), which can be stated as follows: given a graph $G$ and terminals $T$, where each terminal $v in T$ requires a facility of a minimum grade of service $R(v)in {1,2,ldotsell}$, compute a Steiner tree $G$ by installing facilities on a subset of vertices, such that any two vertices requiring a certain grade of service are connected by a path in $G$ with the minimum grade of service or better. Facilities of higher grade are more costly than facilities of lower grade. Multi-level variants such as this one can be useful in network design problems where vertices may require facilities of varying priority. While similar problems have been studied in the edge-weighted case, they have not been studied as well in the more general vertex-weighted case. We first describe a simple heuristic for the V-GSST problem whose approximation ratio depends on $ell$, the number of grades of service. We then generalize the greedy algorithm of [Klein & Ravi, 1995] to show that the V-GSST problem admits a $(2 ln |T|)$-approximation, where $T$ is the set of terminals requiring some facility. This result is surprising, as it shows that the (seemingly harder) multi-grade problem can be approximated as well as the VST problem, and that the approximation ratio does not depend on the number of grades of service.
In the $d$-dimensional hypercube bin packing problem, a given list of $d$-dimensional hypercubes must be packed into the smallest number of hypercube bins. Epstein and van Stee [SIAM J. Comput. 35 (2005)] showed that the asymptotic performance ratio $rho$ of the online bounded space variant is $Omega(log d)$ and $O(d/log d)$, and conjectured that it is $Theta(log d)$. We show that $rho$ is in fact $Theta(d/log d)$, using probabilistic arguments.
We give the first $2$-approximation algorithm for the cluster vertex deletion problem. This is tight, since approximating the problem within any constant factor smaller than $2$ is UGC-hard. Our algorithm combines the previous approaches, based on the local ratio technique and the management of true twins, with a novel construction of a good cost function on the vertices at distance at most $2$ from any vertex of the input graph. As an additional contribution, we also study cluster vertex deletion from the polyhedral perspective, where we prove almost matching upper and lower bounds on how well linear programming relaxations can approximate the problem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
