Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEfficient computation of generalized Ising polynomials on graphs with fixed clique-width
271
0
0.0
(
0
)
Added by
Tomer Kotek
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 and 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 constructive 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
