اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدEfficient computation of generalized Ising polynomials on graphs with fixed clique-width
261
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Graph polynomials which are definable in Monadic Second Order Logic (MSOL) on the vocabulary of graphs are Fixed-Parameter Tractable (FPT) with respect to clique-width. In contrast, graph polynomials which are definable in MSOL on the vocabulary of hypergraphs are fixed-parameter tractable with respect to tree-width, but not necessarily with respect to clique width. No algorithmic meta-theorem is known for the computation of graph polynomials definable in MSOL on the vocabulary of hypergraphs with respect to clique-width. We define an infinite class of such graph polynomials extending the class of graph polynomials definable in MSOL on the vocabulary of graphs and prove that they are Fixed-Parameter Polynomial Time (FPPT) computable, i.e. that they can be computed in time $O(n^{f(k)})$, where $n$ is the number of vertices and $k$ is the clique-width.
قيم البحث
اقرأ أيضاً
Seeses conjecture for finite graphs states that monadic second-order logic (MSO) is undecidable on all graph classes of unbounded clique-width. We show that to establish this it would suffice to show that grids of unbounded size can be interpreted in
two families of graph classes: minimal hereditary classes of unbounded clique-width; and antichains of unbounded clique-width under the induced subgraph relation. We explore a number of known examples of the former category and establish that grids of unbounded size can indeed be interpreted in them.
A graph $G$ contains $H$ as an emph{immersion} if there is an injective mapping $phi: V(H)rightarrow V(G)$ such that for each edge $uvin E(H)$, there is a path $P_{uv}$ in $G$ joining vertices $phi(u)$ and $phi(v)$, and all the paths $P_{uv}$, $uvin
E(H)$, are pairwise edge-disjoint. An analogue of Hadwigers conjecture for the clique immersions by Lescure and Meyniel states that every graph $G$ contains $K_{chi(G)}$ as an immersion. We consider the average degree condition and prove that for any bipartite graph $H$, every $H$-free graph $G$ with average degree $d$ contains a clique immersion of order $(1-o(1))d$, implying that Lescure and Meyniels conjecture holds asymptotically for graphs without fixed bipartite graph.
A visibility algorithm maps time series into complex networks following a simple criterion. The resulting visibility graph has recently proven to be a powerful tool for time series analysis. However its straightforward computation is time-consuming a
nd rigid, motivating the development of more efficient algorithms. Here we present a highly efficient method to compute visibility graphs with the further benefit of flexibility: on-line computation. We propose an encoder/decoder approach, with an on-line adjustable binary search tree codec for time series as well as its corresponding decoder for visibility graphs. The empirical evidence suggests the proposed method for computation of visibility graphs offers an on-line computation solution at no additional computation time cost. The source code is available online.
In this paper, we prove that, given a clique-width $k$-expression of an $n$-vertex graph, textsc{Hamiltonian Cycle} can be solved in time $n^{mathcal{O}(k)}$. This improves the naive algorithm that runs in time $n^{mathcal{O}(k^2)}$ by Espelage et al
. (WG 2001), and it also matches with the lower bound result by Fomin et al. that, unless the Exponential Time Hypothesis fails, there is no algorithm running in time $n^{o(k)}$ (SIAM. J. Computing 2014). We present a technique of representative sets using two-edge colored multigraphs on $k$ vertices. The essential idea is that, for a two-edge colored multigraph, the existence of an Eulerian trail that uses edges with different colors alternately can be determined by two information: the number of colored edges incident with each vertex, and the connectedness of the multigraph. With this idea, we avoid the bottleneck of the naive algorithm, which stores all the possible multigraphs on $k$ vertices with at most $n$ edges.
We introduce a new class of abstract structures, which we call generalized ultrametric semilattices, and in which the meet operation of the semilattice coexists with a generalized distance function in a tightly coordinated way. We prove a constructiv
e fixed-point theorem for strictly contracting functions on directed-complete generalized ultrametric semilattices, and introduce a corresponding induction principle. We cite examples of application in the semantics of logic programming and timed computation, where, until now, the only tool available has been the non-constructive fixed-point theorem of Priess-Crampe and Ribenboim for strictly contracting functions on spherically complete generalized ultrametric semilattices.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
