اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدLinear-Time Recognition of Double-Threshold Graphs
77
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A graph $G = (V,E)$ is a double-threshold graph if there exist a vertex-weight function $w colon V to mathbb{R}$ and two real numbers $mathtt{lb}, mathtt{ub} in mathbb{R}$ such that $uv in E$ if and only if $mathtt{lb} le mathtt{w}(u) + mathtt{w}(v) le mathtt{ub}$. In the literature, those graphs are studied as the pairwise compatibility graphs that have stars as their underlying trees. We give a new characterization of double-threshold graphs, which gives connections to bipartite permutation graphs. Using the new characterization, we present a linear-time algorithm for recognizing double-threshold graphs. Prior to our work, the fastest known algorithm by Xiao and Nagamochi [COCOON 2018] ran in $O(n^6)$ time, where $n$ is the number of vertices.
قيم البحث
اقرأ أيضاً
The interval graph for a set of intervals on a line consists of one vertex for each interval, and an edge for each intersecting pair of intervals. A probe interval graph is a variant that is motivated by an application to genomics, where the interval
s are partitioned into two sets: probes and non-probes. The graph has an edge between two vertices if they intersect and at least one of them is a probe. We give a linear-time algorithm for determining whether a given graph and partition of vertices into probes and non-probes is a probe interval graph. If it is, we give a layout of intervals that proves this. We can also determine whether the layout of the intervals is uniquely constrained within the same time bound. As part of the algorithm, we solve the consecutive-ones probe matrix problem in linear time, develop algorithms for operating on PQ trees, and give results that relate PQ trees for different submatrices of a consecutive-ones matrix.
Best match graphs (BMGs) are vertex-colored digraphs that naturally arise in mathematical phylogenetics to formalize the notion of evolutionary closest genes w.r.t. an a priori unknown phylogenetic tree. BMGs are explained by unique least resolved tr
ees. We prove that the property of a rooted, leaf-colored tree to be least resolved for some BMG is preserved by the contraction of inner edges. For the special case of two-colored BMGs, this leads to a characterization of the least resolved trees (LRTs) of binary-explainable trees and a simple, polynomial-time algorithm for the minimum cardinality completion of the arc set of a BMG to reach a BMG that can be explained by a binary tree.
For every constant $d geq 3$ and $epsilon > 0$, we give a deterministic $mathrm{poly}(n)$-time algorithm that outputs a $d$-regular graph on $Theta(n)$ vertices that is $epsilon$-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by $2sqr
t{d-1} + epsilon$ (excluding the single trivial eigenvalue of~$d$).
The partial representation extension problem generalizes the recognition problem for classes of graphs defined in terms of vertex representations. We exhibit circular-arc graphs as the first example of a graph class where the recognition is polynomia
lly solvable while the representation extension problem is NP-complete. In this setting, several arcs are predrawn and we ask whether this partial representation can be completed. We complement this hardness argument with tractability results of the representation extension problem on various subclasses of circular-arc graphs, most notably on all variants of Helly circular-arc graphs. In particular, we give linear-time algorithms for extending normal proper Helly and proper Helly representations. For normal Helly circular-arc representations we give an $O(n^3)$-time algorithm. Surprisingly, for Helly representations, the complexity hinges on the seemingly irrelevant detail of whether the predrawn arcs have distinct or non-distinct endpoints: In the former case the previous algorithm can be extended, whereas the latter case turns out to be NP-complete. We also prove that representation extension problem of unit circular-arc graphs is NP-complete.
We study the computational complexity of two well-known graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to $H$-free graphs, that is, to graphs that do not contain some fixed gra
ph~$H$ as an induced subgraph. By combining known and new results, we determine the computational complexity of both problems on $H$-free graphs for every graph $H$ except when $H=sP_1+P_4$ for some $sgeq 1$. As part of our approach, we introduce the Subset Vertex Cover problem and prove that it is polynomial-time solvable for $(sP_1+P_4)$-free graphs for every $sgeq 1$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
