Search

The star k-edge-coloring of graph G is a proper edge coloring using k colors such that no path or cycle of length four is bichromatic. The minimum number k for which G admits a star k-edge-coloring is called the star chromatic index of G, denoted by χ′s (G). Let GCD(n, k) be the greatest common divisor of n and k. In this paper, we give a necessary and sufficient condition of χ′s (P (n, k)) = 4 for a generalized Petersen graph P (n, k) and show that “almost all” generalized Petersen graphs have a star 5-edge-colorings. Furthermore, for any two integers k and n (≥2k + 1) such that GCD(n, k) ≥ 3, P (n, k) has a star 5-edge-coloring, with the exception of the case that GCD(n, k) = 3, k ≠ GCD(n, k) and n3≡1(mod3){n \over 3} \equiv 1\left( {\bmod 3} \right).

There is an emerging trend in the Chinese automobile industries that automakers are introducing exclusive enterprise social networks (EESNs) to expand sales and provide after-sale services. The traditional online social networks (OSNs) and enterprise social networks (ESNs), such as X (formerly known as Twitter) and Yammer, are ingeniously designed to facilitate unregulated communications among equal individuals. However, users in EESNs are naturally social stratified, consisting of both enterprise staffs and customers. In addition, the motivation to operate EESNs can be quite complicated, including providing customer services and facilitating communication among enterprise staffs. As a result, the social behaviors in EESNs can be quite different from those in OSNs and ESNs. In this work, we aim to analyze the social behaviors in EESNs. We consider the Chinese car manufacturer NIO as a typical example of EESNs and provide the following contributions. First, we formulate the social behavior analysis in EESNs as a link prediction problem in heterogeneous social networks. Second, to analyze this link prediction problem, we derive plentiful user features and build multiple meta-path graphs for EESNs. Third, we develop a novel Fast (H)eterogeneous graph (A)ttention (N)etwork algorithm for (D)irected graphs (FastHAND) to predict directed social links among users in EESNs. This algorithm introduces feature group attention at the node-level and uses an edge sampling algorithm over directed meta-path graphs to reduce the computation cost. By conducting various experiments on the NIO community data, we demonstrate the predictive power of our proposed FastHAND method. The experimental results also verify our intuitions about social affinity propagation in EESNs. [ABSTRACT FROM AUTHOR]

Decision-making is a basic component of agents' (e.g., intelligent sensors) behaviors, in which one's cognition plays a crucial role in the process and outcome. Extensive games, a class of interactive decision-making scenarios, have been studied in diverse fields. Recently, a model of extensive games was proposed in which agent cognition of the structure of the underlying game and the quality of the game situations are encoded by artificial neural networks. This model refines the classic model of extensive games, and the corresponding equilibrium concept—cognitive perfect equilibrium (CPE)—differs from the classic subgame perfect equilibrium, since CPE takes agent cognition into consideration. However, this model neglects the consideration that game-playing processes are greatly affected by agents' cognition of their opponents. To this end, in this work, we go one step further by proposing a framework in which agents' cognition of their opponents is incorporated. A method is presented for evaluating opponents' cognition about the game being played, and thus, an algorithm designed for playing such games is analyzed. The resulting equilibrium concept is defined as adversarial cognition equilibrium (ACE). By means of a running example, we demonstrate that the ACE is more realistic than the CPE, since it involves learning about opponents' cognition. Further results are presented regarding the computational complexity, soundness, and completeness of the game-solving algorithm and the existence of the equilibrium solution. This model suggests the possibility of enhancing an agent's strategic ability by evaluating opponents' cognition. [ABSTRACT FROM AUTHOR]

The study of intelligent game-playing has gained tremendous attention in the past few decades. The recent development of artificial intelligence (AI) players (e.g., the Go player AlphaGo) has made intelligent game-playing even more prominent in both academia and industry. The performance of state-of-the-art AI players benefits greatly from machine learning techniques, based on which, players can make estimations and decisions even without understanding the games. Although AI machines show great superiority over humans in terms of data processing and complex computation, there remains a vast distance between artificial intelligence and human intelligence with respect to the abilities of context understanding and reasoning. In this paper, we explore the theoretical foundation of intelligent game-playing from a logical perspective. The proposed logic, by considering the computational limits in practical game-playing, drops the ideal assumptions in existing logics for the classical game model. We show that under logical framework, the basis of decision-making for agents in game scenarios can be formally represented and analyzed. Moreover, by characterizing the solutions of games, this logic is able to formalize players' rational decision-making during practical game-playing. [ABSTRACT FROM AUTHOR]

Motivation Gene regulatory networks (GRNs) are a way of describing the interaction between genes, which contribute to revealing the different biological mechanisms in the cell. Reconstructing GRNs based on gene expression data has been a central computational problem in systems biology. However, due to the high dimensionality and non-linearity of large-scale GRNs, accurately and efficiently inferring GRNs is still a challenging task. Results In this article, we propose a new approach, iLSGRN, to reconstruct large-scale GRNs from steady-state and time-series gene expression data based on non-linear ordinary differential equations. Firstly, the regulatory gene recognition algorithm calculates the Maximal Information Coefficient between genes and excludes redundant regulatory relationships to achieve dimensionality reduction. Then, the feature fusion algorithm constructs a model leveraging the feature importance derived from XGBoost (eXtreme Gradient Boosting) and RF (Random Forest) models, which can effectively train the non-linear ordinary differential equations model of GRNs and improve the accuracy and stability of the inference algorithm. The extensive experiments on different scale datasets show that our method makes sensible improvement compared with the state-of-the-art methods. Furthermore, we perform cross-validation experiments on the real gene datasets to validate the robustness and effectiveness of the proposed method. Availability and implementation The proposed method is written in the Python language, and is available at: https://github.com/lab319/iLSGRN. [ABSTRACT FROM AUTHOR]

The minimum vertex cover (MVC) problem is a canonical NP-hard combinatorial optimization problem aiming to find the smallest set of vertices such that every edge has at least one endpoint in the set. This problem has extensive applications in cybersecurity, scheduling, and monitoring link failures in wireless sensor networks (WSNs). Numerous local search algorithms have been proposed to obtain "good" vertex coverage. However, due to the NP-hard nature, it is challenging to efficiently solve the MVC problem, especially on large graphs. In this paper, we propose an efficient local search algorithm for MVC called TIVC, which is based on two main ideas: a 3-improvements (TI) framework with a tiny perturbation and edge selection strategy. We conducted experiments on real-world large instances of a massive graph benchmark. Compared with three state-of-the-art MVC algorithms, TIVC shows superior performance in accuracy and possesses a remarkable ability to identify significantly smaller vertex covers on many graphs. [ABSTRACT FROM AUTHOR]

The payoff of an agent depends on both the environment and the actions of other agents. Thus, the ability to model and predict the strategies and behaviors of other agents in an interactive decision-making scenario is one of the core functionalities in intelligent systems. State-of-the-art methods for opponent modeling mainly use an explicit model of opponents' actions, preferences, targets, etc., that the primary agent uses to make decisions. It is more important for an agent to increase its payoff than to accurately predict opponents' behavior. Therefore, we propose a framework synchronizing the opponent modeling and decision making of the primary agent by incorporating opponent modeling into reinforcement learning. For interactive decisions, the payoff depends not only on the behavioral characteristics of the opponent but also the current state. However, confounding the two obscures the effects of state and action, which then cannot be accurately encoded. To this end, state evaluation is separated from action evaluation in our model. The experimental results from two game environments, a simulated soccer game and a real game called quiz bowl, show that the introduction of opponent modeling can effectively improve decision payoffs. In addition, the proposed framework for opponent modeling outperforms benchmark models. [ABSTRACT FROM AUTHOR]

Purpose: The aim of this study was to reveal the biological function of endoplasmic reticulum stress (ERS)-related genes (ERSGs) in periodontitis, and provide potential ERS diagnostic markers for clinical therapy of periodontitis. Methods: The differentially expressed ERSGs (DE-ERSGs) were reveled based on periodontitis-related microarray dataset in Gene Expression Omnibus (GEO) database and 295 ERS in previous study, followed by a protein–protein interaction network construction. Then, the subtypes of periodontitis were explored, followed by validation with immune cell infiltration and gene set enrichment. Two machine learning algorithms were used to reveal potential ERS diagnostic markers of periodontitis. The diagnostic effect, target drug and immune correlation of these markers were further evaluated. Finally, a microRNA(miRNA)-gene interaction network was constructed. Results: A total of 34 DE-ERSGs were revealed between periodontitis samples and control, followed by two subtypes investigated. There was a significant difference of ERS score, immune infiltration and Hallmark enrichment between two subtypes. Then, totally 7 ERS diagnostic markers including FCGR2B, XBP1, EDEM2, ATP2A3, ERLEC1, HYOU1 and YOD1 were explored, and the v the time-dependent ROC analysis showed a reliable result. In addition, a drug-gene network was constructed with 4 up-regulated ERS diagnostic markers and 24 drugs. Finally, based on 32 interactions, 5 diagnostic markers and 20 miRNAs, a miRNA-target network was constructed. Conclusions: Up-regulated miR-671-5p might take part in the progression of periodontitis via stimulating the expression of ATP2A3. ERSGs including XBP1 and FCGR2B might be novel diagnostic marker for periodontitis. [ABSTRACT FROM AUTHOR]

Given a simple connected graph G, the metric dimension dim (G) (and edge metric dimension edim (G) ) is defined as the cardinality of a smallest vertex subset S ⊆ V (G) for which every two distinct vertices (and edges) in G have distinct distances to a vertex of S. It is an interesting topic to discuss the relation between these two dimensions for some class of graphs. This paper settles two open problems on this topic for unicyclic graphs. We recently learned that Sedlar and Škrekovski settled these problems, but our work presents the results in a completely different way. By introducing four classes of subgraphs, we characterize the structure of a unicyclic graph G such that dim (G) and edim (G) are equal to the cardinality of any minimum branch-resolving set for unicyclic graphs. This generates an approach to determine the exact value of the metric dimension (and edge metric dimension) for a unicyclic graph. [ABSTRACT FROM AUTHOR]

Given a graph whose vertex set is partitioned, the partition coloring problem (PCP) requires the selection of one vertex from each partite set, such that the subgraph induced by the set of the selected vertices has the minimum chromatic number. Motivated by the routing and wavelength assignment problem for optical networks, PCP has been used to model many other real-world applications, such as dichotomy-based constraint encoding and scheduling problems. Solving PCP for large graphs is still a challenge since it is $\mathcal {NP}$ -complete. In this article, we first propose a key concept called a partition independent set (PIS) and design an efficient algorithm called FastPIS to find a maximum PIS. By applying FastPIS with a simple coloring procedure, we can obtain a high-quality initial solution for PCP. Moreover, we propose a reduction rule based on another novel concept called an $\ell $ -clustering-degree bound ordered set ($\ell $ -CDBOS), by which the scale of the working graph can be iteratively reduced. Based on these techniques, we develop an efficient method called HotPGC for solving PCP. The proposed algorithm is evaluated on benchmark graphs, and computational results show that HotPGC achieves highly competitive performance, compared with the state-of-the-art algorithms. The influence of the proposed reduction rule on the efficiency of HotPGC is also analyzed. [ABSTRACT FROM AUTHOR]

DeoxyriboNucleic Acid (DNA) encryption is a new encryption method that appeared along with the research of DNA nanotechnology in recent years. Due to the complexity of biology in DNA nanotechnology, DNA encryption brings in an additional difficulty in deciphering and, thus, can enhance information security. As a new approach in DNA nanotechnology, DNA strand displacement has particular advantages such as being enzyme free and self-assembly. However, the existing research on DNA-strand-displacement-based encryption has mostly stayed at a theoretical or simulation stage. To this end, this paper proposes a new DNA-strand-displacement-based encryption framework. This encryption framework involves three main strategies. The first strategy was a tri-phase conversion from plaintext to DNA sequences according to a Huffman-coding-based transformation rule, which enhances the concealment of the information. The second strategy was the development of DNA strand displacement molecular modules, which produce the initial key for information encryption. The third strategy was a cyclic-shift-based operation to extend the initial key long enough, and thus increase the deciphering difficulty. The results of simulation and biological experiments demonstrated the feasibility of our scheme for encryption. The approach was further validated in terms of the key sensitivity, key space, and statistic characteristic. Our encryption framework provides a potential way to realize DNA-strand-displacement-based encryption via biological experiments and promotes the research on DNA-strand-displacement-based encryption. [ABSTRACT FROM AUTHOR]

Game theory has become a standard tool for depicting and demonstrating various game‐like phenomena by providing appropriate mathematical models and for analyzing and predicting agents' behaviors and their decisions by formalizing solution concepts. The conventional game model mainly concerns ideal systems that would always guarantee optimal responses, which appears unrealistic for practical game scenarios since decision‐making usually entails resource costs. Therefore, this study considers players' decision‐making in extensive games when the computational cost of searching the strategy space is limited. We start with a new mathematical model of extensive games that features a bound on computational resources during players' decision‐making process such that they can only foresee a part of the available alternatives in the future. This model is more appropriate in predicting players' strategies than the conventional model, under which we investigate the effects of computational costs on players' strategies as well as the computational complexity. Furthermore, a simulation experiment is performed to seek the connection between the amount of resources and the goodness of the outcomes. This study is expected to provide a foundation for players' rational decision‐making with computational costs. [ABSTRACT FROM AUTHOR]

A total k -coloring of a graph is an assignment of k colors to its vertices and edges such that no two adjacent or incident elements receive the same color. The total coloring conjecture (TCC) states that every simple graph G has a total Δ G + 2 -coloring, where Δ G is the maximum degree of G. This conjecture has been confirmed for planar graphs with maximum degree at least 7 or at most 5, i.e., the only open case of TCC is that of maximum degree 6. It is known that every planar graph G of Δ G ≥ 9 or Δ G ∈ 7,8 with some restrictions has a total Δ G + 1 -coloring. In particular, in (Shen and Wang, 2009), the authors proved that every planar graph with maximum degree 6 and without 4-cycles has a total 7-coloring. In this paper, we improve this result by showing that every diamond-free and house-free planar graph of maximum degree 6 is totally 7-colorable if every 6-vertex is not incident with two adjacent four cycles or three cycles of size p , q , ℓ for some p , q , ℓ ∈ 3,4,4 , 3,3,4 . [ABSTRACT FROM AUTHOR]

An acyclic colouring of a graph is a proper colouring of the graph, for which every cycle uses at least three colours. In this paper, we describe a method for constructing all 4-connected acyclically 4-colourable planar triangulations that have exactly four odd-vertices, except the ones that contain no adjacent odd-vertices. Unlike previous operations, our method successfully establishes a connection with (acyclic) 4-colourings. Moreover, we discuss a special class of graphs, called diamond triangulations, and give a necessary and sufficient condition for a diamond triangulation to be acyclically 4-colourable. [ABSTRACT FROM AUTHOR]

A graphGis uniquelyk-colourable if the chromatic number ofGiskandGhas only onek-colouring up to permutation of the colours. Aksionov [On uniquely 3-colorable planar graphs, Discrete Math. 20 (1977), pp. 209–216] conjectured that every uniquely 3-colourable planar graph with at least four vertices has two adjacent triangles. However, in the same year, Melnikov and Steinberg [L.S. Mel'nikov and R. Steinberg,One counterexample for two conjectures on three coloring, Discrete Math. 20 (1977), pp. 203–206.] disproved the conjecture by constructing a counterexample. In this paper, we prove that if a uniquely 3-colourable planar graphGhas at most 4 triangles thenGhas two adjacent triangles. Furthermore, for any, we construct a uniquely 3-colourable planar graph withktriangles and without adjacent triangles. [ABSTRACT FROM PUBLISHER]

This paper proposes a quick exact algorithm for the graph coloring problem. The algorithm is based on implicit enumerating the coloring sequences of graph and converting the conflict edges constraints into carry numbers, which avoid exponential unnecessary graph coloring sequences testing. Only polynomial memory is needed in our algorithm, and symmetrical coloring solutions obtained by color permutations were removed. The algorithm performs reasonably well on a set of 61 benchmark graphs. [ABSTRACT FROM AUTHOR]

For a graph G, its k-rainbow independent domination number, written as γ rik (G) , is defined as the cardinality of a minimum set consisting of k vertex-disjoint independent sets V 1 , V 2 , ... , V k such that every vertex in V 0 = V (G) \ (∪ i = 1 k V i) has a neighbor in V i for all i ∈ { 1 , 2 , ... , k } . This domination invariant was proposed by Kraner Šumenjak, Rall and Tepeh (in Applied Mathematics and Computation 333(15), 2018: 353–361), which aims to compute the independent domination number of G □ K k (the generalized prism) via studying the problem of integer labeling on G. They proved a Nordhaus–Gaddum-type theorem: 5 ≤ γ ri 2 (G) + γ ri 2 (G ¯) ≤ n + 3 for any n-order graph G with n ≥ 3 , in which G ¯ denotes the complement of G. This work improves their result and shows that if G ≇ C 5 , then 5 ≤ γ ri 2 (G) + γ ri 2 (G ¯) ≤ n + 2 . [ABSTRACT FROM AUTHOR]

A graph G is uniquely k-colorable if the chromatic number of G is k and G has only one k-coloring up to the permutation of the colors. For a plane graph G, two faces f 1 and f 2 of G are adjacent (i , j) -faces if d (f 1) = i , d (f 2) = j , and f 1 and f 2 have a common edge, where d (f) is the degree of a face f. In this paper, we prove that every uniquely three-colorable plane graph has adjacent (3 , k) -faces, where k ≤ 5 . The bound of five for k is the best possible. Furthermore, we prove that there exists a class of uniquely three-colorable plane graphs having neither adjacent (3 , i) -faces nor adjacent (3 , j) -faces, where i , j are fixed in { 3 , 4 , 5 } and i ≠ j . One of our constructions implies that there exists an infinite family of edge-critical uniquely three-colorable plane graphs with n vertices and 7 3 n - 14 3 edges, where n (≥ 11) is odd and n ≡ 2 (mod 3) . [ABSTRACT FROM AUTHOR]

The concept of a metric dimension was proposed to model robot navigation where the places of navigating agents can change among nodes. The metric dimension m d (G) of a graph G is the smallest number k for which G contains a vertex set W, such that | W | = k and every pair of vertices of G possess different distances to at least one vertex in W. In this paper, we demonstrate that m d (H D N 1 (n)) = 4 for n ≥ 2 . This indicates that in these types of hex derived sensor networks, the least number of nodes needed for locating any other node is four. [ABSTRACT FROM AUTHOR]

Due to its wide application, deep reinforcement learning (DRL) has been extensively studied in the motion planning community in recent years. However, in the current DRL research, regardless of task completion, the state information of the agent will be reset afterward. This leads to a low sample utilization rate and hinders further explorations of the environment. Moreover, in the initial training stage, the agent has a weak learning ability in general, which affects the training efficiency in complex tasks. In this study, a new hierarchical reinforcement learning (HRL) framework dubbed hierarchical learning based on game playing with state relay (HGR) is proposed. In particular, we introduce an auxiliary penalty to regulate task difficulty, and one training mechanism, the state relay mechanism, is designed. The relay mechanism can make full use of the intermediate states of the agent and expand the environment exploration of low-level policy. Our algorithm can improve the sample utilization rate, reduce the sparse reward problem, and thereby enhance the training performance in complex environments. Simulation tests are carried out on two public experiment platforms, i.e., MazeBase and MuJoCo, to verify the effectiveness of the proposed method. The results show that HGR significantly benefits the reinforcement learning (RL) area.