اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAlgorithm and Complexity for a Network Assortativity Measure
143
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We show that finding a graph realization with the minimum Randic index for a given degree sequence is solvable in polynomial time by formulating the problem as a minimum weight perfect b-matching problem. However, the realization found via this reduction is not guaranteed to be connected. Approximating the minimum weight b-matching problem subject to a connectivity constraint is shown to be NP-Hard. For instances in which the optimal solution to the minimum Randic index problem is not connected, we describe a heuristic to connect the graph using pairwise edge exchanges that preserves the degree sequence. In our computational experiments, the heuristic performs well and the Randic index of the realization after our heuristic is within 3% of the unconstrained optimal value on average. Although we focus on minimizing the Randic index, our results extend to maximizing the Randic index as well. Applications of the Randic index to synchronization of neuronal networks controlling respiration in mammals and to normalizing cortical thickness networks in diagnosing individuals with dementia are provided.
قيم البحث
اقرأ أيضاً
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 th
e 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.
A split graph is a graph whose vertex set can be partitioned into a clique and a stable set. Given a graph $G$ and weight function $w: V(G) to mathbb{Q}_{geq 0}$, the Split Vertex Deletion (SVD) problem asks to find a minimum weight set of vertices $
X$ such that $G-X$ is a split graph. It is easy to show that a graph is a split graph if and only it it does not contain a $4$-cycle, $5$-cycle, or a two edge matching as an induced subgraph. Therefore, SVD admits an easy $5$-approximation algorithm. On the other hand, for every $delta >0$, SVD does not admit a $(2-delta)$-approximation algorithm, unless P=NP or the Unique Games Conjecture fails. For every $epsilon >0$, Lokshtanov, Misra, Panolan, Philip, and Saurabh recently gave a randomized $(2+epsilon)$-approximation algorithm for SVD. In this work we give an extremely simple deterministic $(2+epsilon)$-approximation algorithm for SVD.
A path in an(a) edge(vertex)-colored graph is called emph{a conflict-free path} if there exists a color used on only one of its edges(vertices). An(A) edge(vertex)-colored graph is called emph{conflict-free (vertex-)connected} if there is a conflict-
free path between each pair of distinct vertices. We call the graph $G$ emph{strongly conflict-free connected }if there exists a conflict-free path of length $d_G(u,v)$ for every two vertices $u,vin V(G)$. And the emph{strong conflict-free connection number} of a connected graph $G$, denoted by $scfc(G)$, is defined as the smallest number of colors that are required to make $G$ strongly conflict-free connected. In this paper, we first investigate the question: Given a connected graph $G$ and a coloring $c: E(or V)rightarrow {1,2,cdots,k} (kgeq 1)$ of the graph, determine whether or not $G$ is, respectively, conflict-free connected, vertex-conflict-free connected, strongly conflict-free connected under coloring $c$. We solve this question by providing polynomial-time algorithms. We then show that it is NP-complete to decide whether there is a k-edge-coloring $(kgeq 2)$ of $G$ such that all pairs $(u,v)in P (Psubset Vtimes V)$ are strongly conflict-free connected. Finally, we prove that the problem of deciding whether $scfc(G)leq k$ $(kgeq 2)$ for a given graph $G$ is NP-complete.
We study variants of Mastermind, a popular board game in which the objective is sequence reconstruction. In this two-player game, the so-called textit{codemaker} constructs a hidden sequence $H = (h_1, h_2, ldots, h_n)$ of colors selected from an alp
habet $mathcal{A} = {1,2,ldots, k}$ (textit{i.e.,} $h_iinmathcal{A}$ for all $iin{1,2,ldots, n}$). The game then proceeds in turns, each of which consists of two parts: in turn $t$, the second player (the textit{codebreaker}) first submits a query sequence $Q_t = (q_1, q_2, ldots, q_n)$ with $q_iin mathcal{A}$ for all $i$, and second receives feedback $Delta(Q_t, H)$, where $Delta$ is some agreed-upon function of distance between two sequences with $n$ components. The game terminates when $Q_t = H$, and the codebreaker seeks to end the game in as few turns as possible. Throughout we let $f(n,k)$ denote the smallest integer such that the codebreaker can determine any $H$ in $f(n,k)$ turns. We prove three main results: First, when $H$ is known to be a permutation of ${1,2,ldots, n}$, we prove that $f(n, n)ge n - loglog n$ for all sufficiently large $n$. Second, we show that Knuths Minimax algorithm identifies any $H$ in at most $nk$ queries. Third, when feedback is not received until all queries have been submitted, we show that $f(n,k)=Omega(nlog k)$.
Traditionally, network analysis is based on local properties of vertices, like their degree or clustering, and their statistical behavior across the network in question. This paper develops an approach which is different in two respects. We investiga
te edge-based properties, and we define global characteristics of networks directly. The latter will provide our affirmative answer to the question raised in the title. More concretely, we start with Formans notion of the Ricci curvature of a graph, or more generally, a polyhedral complex. This will allow us to pass from a graph as representing a network to a polyhedral complex for instance by filling in triangles into connected triples of edges and to investigate the resulting effect on the curvature. This is insightful for two reasons: First, we can define a curvature flow in order to asymptotically simplify a network and reduce it to its essentials. Second, using a construction of Bloch, which yields a discrete Gauss-Bonnet theorem, we have the Euler characteristic of a network as a global characteristic. These two aspects beautifully merge in the sense that the asymptotic properties of the curvature flow are indicated by that Euler characteristic.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
