亚洲男人的天堂2018av,欧美草比,久久久久久免费视频精选,国色天香在线看免费,久久久久亚洲av成人片仓井空

Given a graph $G$ with a fixed vertex order $\prec$, one obtains a circle graph $H$ whose vertices are the edges of $G$ and where two such edges are adjacent if and only if their endpoints are pairwise distinct and alternate in $\prec$. Therefore, the problem of determining whether $G$ has a $k$-page book embedding with spine order $\prec$ is equivalent to deciding whether $H$ can be colored with $k$ colors. Finding a $k$-coloring for a circle graph is known to be NP-complete for $k \geq 4$ and trivial for $k \leq 2$. For $k = 3$, Unger (1992) claims an efficient algorithm that finds a 3-coloring in $O(n \log n)$ time, if it exists. Given a circle graph $H$, Unger's algorithm (1) constructs a 3-\textsc{Sat} formula $\Phi$ that is satisfiable if and only if $H$ admits a 3-coloring and (2) solves $\Phi$ by a backtracking strategy that relies on the structure imposed by the circle graph. However, the extended abstract misses several details and Unger refers to his PhD thesis (in German) for details. In this paper we argue that Unger's algorithm for 3-coloring circle graphs is not correct and that 3-coloring circle graphs should be considered as an open problem. We show that step (1) of Unger's algorithm is incorrect by exhibiting a circle graph whose formula $\Phi$ is satisfiable but that is not 3-colorable. We further show that Unger's backtracking strategy for solving $\Phi$ in step (2) may produce incorrect results and give empirical evidence that it exhibits a runtime behaviour that is not consistent with the claimed running time.

We consider the problem of computing the Maximal Exact Matches (MEMs) of a given pattern $P[1 .. m]$ on a large repetitive text collection $T[1 .. n]$, which is represented as a (hopefully much smaller) run-length context-free grammar of size $g_{rl}$. We show that the problem can be solved in time $O(m^2 \log^\epsilon n)$, for any constant $\epsilon > 0$, on a data structure of size $O(g_{rl})$. Further, on a locally consistent grammar of size $O(\delta\log\frac{n}{\delta})$, the time decreases to $O(m\log m(\log m + \log^\epsilon n))$. The value $\delta$ is a function of the substring complexity of $T$ and $\Omega(\delta\log\frac{n}{\delta})$ is a tight lower bound on the compressibility of repetitive texts $T$, so our structure has optimal size in terms of $n$ and $\delta$. We extend our results to several related problems, such as finding $k$-MEMs, MUMs, rare MEMs, and applications.

Two new qubit stabilizer codes with parameters $[77, 0, 19]_2$ and $[90, 0, 22]_2$ are constructed for the first time by employing additive symplectic self-dual $\F_4$ codes from multidimensional circulant (MDC) graphs. We completely classify MDC graph codes for lengths $4\le n \le 40$ and show that many optimal $\dsb{\ell, 0, d}$ qubit codes can be obtained from the MDC construction. Moreover, we prove that adjacency matrices of MDC graphs have nested block circulant structure and determine isomorphism properties of MDC graphs.

Given a binary word relation $\tau$ onto $A^*$ and a finite language $X\subseteq A^*$, a $\tau$-Gray cycle over $X$ consists in a permutation $\left(w_{[i]}\right)_{0\le i\le |X|-1}$ of $X$ such that each word $w_{[i]}$ is an image under $\tau$ of the previous word $w_{{[i-1]}}$. We define the complexity measure $\lambda_{A,\tau}(n)$, equal to the largest cardinality of a language $X$ having words of length at most $n$, and s.t. some $\tau$-Gray cycle over $X$ exists. The present paper is concerned with $\tau=\sigma_k$, the so-called $k$-character substitution, s.t. $(u,v)\in\sigma_k$ holds if, and only if, the Hamming distance of $u$ and $v$ is $k$. We present loopless (resp., constant amortized time) algorithms for computing specific maximum length $$\sigma_k$-Gray cycles.

Broadcast protocols enable a set of $n$ parties to agree on the input of a designated sender, even facing attacks by malicious parties. In the honest-majority setting, randomization and cryptography were harnessed to achieve low-communication broadcast with sub-quadratic total communication and balanced sub-linear cost per party. However, comparatively little is known in the dishonest-majority setting. Here, the most communication-efficient constructions are based on Dolev and Strong (SICOMP '83), and sub-quadratic broadcast has not been achieved. On the other hand, the only nontrivial $\omega(n)$ communication lower bounds are restricted to deterministic protocols, or against strong adaptive adversaries that can perform "after the fact" removal of messages. We provide new communication lower bounds in this space, which hold against arbitrary cryptography and setup assumptions, as well as a simple protocol showing near tightness of our first bound. 1) We demonstrate a tradeoff between resiliency and communication for protocols secure against $n-o(n)$ static corruptions. For example, $\Omega(n\cdot {\sf polylog}(n))$ messages are needed when the number of honest parties is $n/{\sf polylog}(n)$; $\Omega(n\sqrt{n})$ messages are needed for $O(\sqrt{n})$ honest parties; and $\Omega(n^2)$ messages are needed for $O(1)$ honest parties. Complementarily, we demonstrate broadcast with $O(n\cdot{\sf polylog}(n))$ total communication facing any constant fraction of static corruptions. 2) Our second bound considers $n/2 + k$ corruptions and a weakly adaptive adversary that cannot remove messages "after the fact." We show that any broadcast protocol within this setting can be attacked to force an arbitrary party to send messages to $k$ other parties. This rules out, for example, broadcast facing 51% corruptions in which all non-sender parties have sublinear communication locality.

A pair $\langle G_0, G_1 \rangle$ of graphs admits a mutual witness proximity drawing $\langle \Gamma_0, \Gamma_1 \rangle$ when: (i) $\Gamma_i$ represents $G_i$, and (ii) there is an edge $(u,v)$ in $\Gamma_i$ if and only if there is no vertex $w$ in $\Gamma_{1-i}$ that is ``too close'' to both $u$ and $v$ ($i=0,1$). In this paper, we consider infinitely many definitions of closeness by adopting the $\beta$-proximity rule for any $\beta \in [1,\infty]$ and study pairs of isomorphic trees that admit a mutual witness $\beta$-proximity drawing. Specifically, we show that every two isomorphic trees admit a mutual witness $\beta$-proximity drawing for any $\beta \in [1,\infty]$. The constructive technique can be made ``robust'': For some tree pairs we can suitably prune linearly many leaves from one of the two trees and still retain their mutual witness $\beta$-proximity drawability. Notably, in the special case of isomorphic caterpillars and $\beta=1$, we construct linearly separable mutual witness Gabriel drawings.

We study the following problem: Given a set $S$ of $n$ points in the plane, how many edge-disjoint plane straight-line spanning paths of $S$ can one draw? A well known result is that when the $n$ points are in convex position, $\lfloor n/2\rfloor$ such paths always exist, but when the points of $S$ are in general position the only known construction gives rise to two edge-disjoint plane straight-line spanning paths. In this paper, we show that for any set $S$ of at least ten points, no three of which are collinear, one can draw at least three edge-disjoint plane straight-line spanning paths of~$S$. Our proof is based on a structural theorem on halving lines of point configurations and a strengthening of the theorem about two spanning paths, which we find interesting in its own right: if $S$ has at least six points, and we prescribe any two points on the boundary of its convex hull, then the set contains two edge-disjoint plane spanning paths starting at the prescribed points.

Large Language Models (LLMs) have shown promise in multiple software engineering tasks including code generation, code summarisation, test generation and code repair. Fault localisation is essential for facilitating automatic program debugging and repair, and is demonstrated as a highlight at ChatGPT-4's launch event. Nevertheless, there has been little work understanding LLMs' capabilities for fault localisation in large-scale open-source programs. To fill this gap, this paper presents an in-depth investigation into the capability of ChatGPT-3.5 and ChatGPT-4, the two state-of-the-art LLMs, on fault localisation. Using the widely-adopted Defects4J dataset, we compare the two LLMs with the existing fault localisation techniques. We also investigate the stability and explanation of LLMs in fault localisation, as well as how prompt engineering and the length of code context affect the fault localisation effectiveness. Our findings demonstrate that within a limited code context, ChatGPT-4 outperforms all the existing fault localisation methods. Additional error logs can further improve ChatGPT models' localisation accuracy and stability, with an average 46.9% higher accuracy over the state-of-the-art baseline SmartFL in terms of TOP-1 metric. However, performance declines dramatically when the code context expands to the class-level, with ChatGPT models' effectiveness becoming inferior to the existing methods overall. Additionally, we observe that ChatGPT's explainability is unsatisfactory, with an accuracy rate of only approximately 30%. These observations demonstrate that while ChatGPT can achieve effective fault localisation performance under certain conditions, evident limitations exist. Further research is imperative to fully harness the potential of LLMs like ChatGPT for practical fault localisation applications.

We consider the problem of dynamically maintaining the convex hull of a set $S$ of points in the plane under the following special sequence of insertions and deletions (called {\em window-sliding updates}): insert a point to the right of all points of $S$ and delete the leftmost point of $S$. We propose an $O(|S|)$-space data structure that can handle each update in $O(1)$ amortized time, such that standard binary-search-based queries on the convex hull of $S$ can be answered in $O(\log h)$ time, where $h$ is the number of vertices of the convex hull of $S$, and the convex hull itself can be output in $O(h)$ time.

Given $k$ input graphs $G_1, \dots ,G_k$, where each pair $G_i$, $G_j$ with $i \neq j$ shares the same graph $G$, the problem Simultaneous Embedding With Fixed Edges (SEFE) asks whether there exists a planar drawing for each input graph such that all drawings coincide on $G$. While SEFE is still open for the case of two input graphs, the problem is NP-complete for $k \geq 3$ [Schaefer, JGAA 13]. In this work, we explore the parameterized complexity of SEFE. We show that SEFE is FPT with respect to $k$ plus the vertex cover number or the feedback edge set number of the the union graph $G^\cup = G_1 \cup \dots \cup G_k$. Regarding the shared graph $G$, we show that SEFE is NP-complete, even if $G$ is a tree with maximum degree 4. Together with a known NP-hardness reduction [Angelini et al., TCS 15], this allows us to conclude that several parameters of $G$, including the maximum degree, the maximum number of degree-1 neighbors, the vertex cover number, and the number of cutvertices are intractable. We also settle the tractability of all pairs of these parameters. We give FPT algorithms for the vertex cover number plus either of the first two parameters and for the number of cutvertices plus the maximum degree, whereas we prove all remaining combinations to be intractable.