Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSome Preliminary Result About the Inset Edge and Average Distance of Trees
40
0
0.0
(
0
)
Added by
M.H. Khalifeh
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
An added edge to a graph is called an inset edge. Predicting k inset edges which minimize the average distance of a graph is known to be NP-Hard. However, when k = 1 the complexity of the problem is polynomial. In this paper, some tools for a precise analysis of the problem for the trees are established. Using the tools, we can avoid using the distance matrix. This leads to more efficient algorithms and a better analysis of the problem. Several applications of the tools as well as a tight bound for the change of average distance when an inset edge is added to a tree are presented.
rate research
Read More
An added edge to a graph is called an inset edge. Predicting k inset edges which minimize the average distance of a graph is known to be NP-Hard. When k = 1 the complexity of the problem is polynomial. In this paper, we further find the single inset edge(s) of a tree with the closest change on the average distance to a given input. To do that we may require the effect of each inset edge for the set of inset edges. For this, we propose an algorithm with the time complexity between O(m) and O(m/m) and an average of less than O( m.log(m)), where m stands for the number of possible inset edges. Then it takes up to O(log(m)) to find the target inset edges for a custom change on the average distance. Using theoretical tools, the algorithm strictly avoids recalculating the distances with no changes, after adding a new edge to a tree. Then reduces the time complexity of calculating remaining distances using some matrix tools which first introduced in [8] with one additional technique. This gives us a dynamic time complexity and absolutely depends on the input tree which is proportion to the Wiener index of the input tree.
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 differe
Positive semidefinite rank (PSD-rank) is a relatively new quantity with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix $M$ as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.
Among many topological indices of trees the sum of distances $sigma(T)$ and the number of subtrees $F(T)$ have been a long standing pair of graph invariants that are well known for their negative correlation. That is, among various given classes of trees, the extremal structures maximizing one usually minimize the other, and vice versa. By introducing the local
We identify a new notion of pseudorandomness for randomness sources, which we call the average bias. Given a distribution $Z$ over ${0,1}^n$, its average bias is: $b_{text{av}}(Z) =2^{-n} sum_{c in {0,1}^n} |mathbb{E}_{z sim Z}(-1)^{langle c, zrangle}|$. A source with average bias at most $2^{-k}$ has min-entropy at least $k$, and so low average bias is a stronger condition than high min-entropy. We observe that the inner product function is an extractor for any source with average bias less than $2^{-n/2}$. The notion of average bias especially makes sense for polynomial sources, i.e., distributions sampled by low-degree $n$-variate polynomials over $mathbb{F}_2$. For the well-studied case of affine sources, it is easy to see that min-entropy $k$ is exactly equivalent to average bias of $2^{-k}$. We show that for quadratic sources, min-entropy $k$ implies that the average bias is at most $2^{-Omega(sqrt{k})}$. We use this relation to design dispersers for separable quadratic sources with a min-entropy guarantee.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
