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

We make progress toward a characterization of the graphs $H$ such that every connected $H$-free graph has a longest path transversal of size $1$. In particular, we show that the graphs $H$ on at most $4$ vertices satisfying this property are exactly the linear forests. We also show that if the order of a connected graph $G$ is large relative to its connectivity $\kappa(G)$, and its independence number $\alpha(G)$ satisfies $\alpha(G) \le \kappa(G) + 2$, then each vertex of maximum degree forms a longest path transversal of size $1$.

Knowledge graphs (KGs) are key tools in many AI-related tasks such as reasoning or question answering. This has, in turn, propelled research in link prediction in KGs, the task of predicting missing relationships from the available knowledge. Solutions based on KG embeddings have shown promising results in this matter. On the downside, these approaches are usually unable to explain their predictions. While some works have proposed to compute post-hoc rule explanations for embedding-based link predictors, these efforts have mostly resorted to rules with unbounded atoms, e.g., bornIn(x,y) => residence(x,y), learned on a global scope, i.e., the entire KG. None of these works has considered the impact of rules with bounded atoms such as nationality(x,England) => speaks(x, English), or the impact of learning from regions of the KG, i.e., local scopes. We therefore study the effects of these factors on the quality of rule-based explanations for embedding-based link predictors. Our results suggest that more specific rules and local scopes can improve the accuracy of the explanations. Moreover, these rules can provide further insights about the inner-workings of KG embeddings for link prediction.

In this paper, we present efficient distributed algorithms for classical symmetry breaking problems, maximal independent sets (MIS) and ruling sets, in power graphs. We work in the standard CONGEST model of distributed message passing, where the communication network is abstracted as a graph $G$. Typically, the problem instance in CONGEST is identical to the communication network $G$, that is, we perform the symmetry breaking in $G$. In this work, we consider a setting where the problem instance corresponds to a power graph $G^k$, where each node of the communication network $G$ is connected to all of its $k$-hop neighbors. Our main contribution is a deterministic polylogarithmic time algorithm for computing $k$-ruling sets of $G^k$, which (for $k>1$) improves exponentially on the current state-of-the-art runtimes. The main technical ingredient for this result is a deterministic sparsification procedure which may be of independent interest. On top of being a natural family of problems, ruling sets (in power graphs) are well-motivated through their applications in the powerful shattering framework [BEPS JACM'16, Ghaffari SODA'19] (and others). We present randomized algorithms for computing maximal independent sets and ruling sets of $G^k$ in essentially the same time as they can be computed in $G$. We also revisit the shattering algorithm for MIS [BEPS JACM'16] and present different approaches for the post-shattering phase. Our solutions are algorithmically and analytically simpler (also in the LOCAL model) than existing solutions and obtain the same runtime as [Ghaffari SODA'16].

A $hole$ is an induced cycle of length at least four, and an odd hole is a hole of odd length. A {\em fork} is a graph obtained from $K_{1,3}$ by subdividing an edge once. An {\em odd balloon} is a graph obtained from an odd hole by identifying respectively two consecutive vertices with two leaves of $K_{1, 3}$. A {\em gem} is a graph that consists of a $P_4$ plus a vertex adjacent to all vertices of the $P_4$. A {\em butterfly} is a graph obtained from two traingles by sharing exactly one vertex. A graph $G$ is perfectly divisible if for each induced subgraph $H$ of $G$, $V(H)$ can be partitioned into $A$ and $B$ such that $H[A]$ is perfect and $\omega(H[B])<\omega(H)$. In this paper, we show that (odd balloon, fork)-free graphs are perfectly divisible (this generalizes some results of Karthick {\em et al}). As an application, we show that $\chi(G)\le\binom{\omega(G)+1}{2}$ if $G$ is (fork, gem)-free or (fork, butterfly)-free.

Let $E=\{e_1,\ldots,e_n\}$ be a set of $C$-oriented disjoint segments in the plane, where $C$ is a given finite set of orientations that spans the plane, and let $s$ and $t$ be two points. %(We also require that for each orientation in $C$, its opposite orientation is also in $C$.) We seek a minimum-link $C$-oriented tour of $E$, that is, a polygonal path $\pi$ from $s$ to $t$ that visits the segments of $E$ in order, such that, the orientations of its edges are in $C$ and their number is minimum. We present an algorithm for computing such a tour in $O(|C|^2 \cdot n^2)$ time. This problem already captures most of the difficulties occurring in the study of the more general problem, in which $E$ is a set of not-necessarily-disjoint $C$-oriented polygons.

In this paper we analyse two-player games by their response graphs. The response graph has nodes which are strategy profiles, with an arc between profiles if they differ in the strategy of a single player, with the direction of the arc indicating the preferred option for that player. Response graphs, and particularly their sink strongly connected components, play an important role in modern techniques in evolutionary game theory and multi-agent learning. We show that the response graph is a simple and well-motivated model of strategic interaction which captures many non-trivial properties of a game, despite not depending on cardinal payoffs. We characterise the games which share a response graph with a zero-sum or potential game respectively, and demonstrate a duality between these sets. This allows us to understand the influence of these properties on the response graph. The response graphs of Matching Pennies and Coordination are shown to play a key role in all two-player games: every non-iteratively-dominated strategy takes part in a subgame with these graph structures. As a corollary, any game sharing a response graph with both a zero-sum game and potential game must be dominance-solvable. Finally, we demonstrate our results on some larger games.

For many real-world decision-making problems subject to uncertainty, it may be essential to deal with multiple and often conflicting objectives while taking the decision-makers' risk preferences into account. Conditional value-at-risk (CVaR) is a widely applied risk measure to address risk-averseness of the decision-makers. In this paper, we use the subset-based polyhedral representation of the CVaR to reformulate the bi-objective two-stage stochastic facility location problem presented in Nazemi et al. (2021). We propose an approximate cutting-plane method to deal with this more computationally challenging subset-based formulation. Then, the cutting plane method is embedded into the epsilon-constraint method, the balanced-box method, and a recently developed matheuristic method to address the bi-objective nature of the problem. Our computational results show the effectiveness of the proposed method. Finally, we discuss how incorporating an approximation of the subset-based polyhedral formulation affects the obtained solutions.

Partitioning the vertices of a (hyper)graph into k roughly balanced blocks such that few (hyper)edges run between blocks is a key problem for large-scale distributed processing. A current trend for partitioning huge (hyper)graphs using low computational resources are streaming algorithms. In this work, we propose FREIGHT: a Fast stREamInG Hypergraph parTitioning algorithm which is an adaptation of the widely-known graph-based algorithm Fennel. By using an efficient data structure, we make the overall running of FREIGHT linearly dependent on the pin-count of the hypergraph and the memory consumption linearly dependent on the numbers of nets and blocks. The results of our extensive experimentation showcase the promising performance of FREIGHT as a highly efficient and effective solution for streaming hypergraph partitioning. Our algorithm demonstrates competitive running time with the Hashing algorithm, with a difference of a maximum factor of four observed on three fourths of the instances. Significantly, our findings highlight the superiority of FREIGHT over all existing (buffered) streaming algorithms and even the in-memory algorithm HYPE, with respect to both cut-net and connectivity measures. This indicates that our proposed algorithm is a promising hypergraph partitioning tool to tackle the challenge posed by large-scale and dynamic data processing.

In the Internet-of-Things (IoT), massive sensitive and confidential information is transmitted wirelessly, making security a serious concern. This is particularly true when technologies, such as non-orthogonal multiple access (NOMA), are used, making it possible for users to access each other's data. This paper studies secure communications in multiuser NOMA downlink systems, where each user is potentially an eavesdropper. Resource allocation is formulated to achieve the maximum sum secrecy rate, meanwhile satisfying the users' data requirements and power constraint. We solve this non-trivial, mixed-integer non-linear programming problem by decomposing it into power allocation with a closed-form solution, and user pairing obtained effectively using linear programming relaxation and barrier algorithm. These subproblems are solved iteratively until convergence, with the convergence rate rigorously analyzed. Simulations demonstrate that our approach outperforms its existing alternatives significantly in the sum secrecy rate and computational complexity.

Graph neural networks (GNNs) are a popular class of machine learning models whose major advantage is their ability to incorporate a sparse and discrete dependency structure between data points. Unfortunately, GNNs can only be used when such a graph-structure is available. In practice, however, real-world graphs are often noisy and incomplete or might not be available at all. With this work, we propose to jointly learn the graph structure and the parameters of graph convolutional networks (GCNs) by approximately solving a bilevel program that learns a discrete probability distribution on the edges of the graph. This allows one to apply GCNs not only in scenarios where the given graph is incomplete or corrupted but also in those where a graph is not available. We conduct a series of experiments that analyze the behavior of the proposed method and demonstrate that it outperforms related methods by a significant margin.