Tight upper bound on the number of edges in a bipartite K3,3-free or K5-free graph with an application

We show that an n-vertex bipartite K_3,3-free graph with n?3 has at most 2n−4 edges and that an n-vertex bipartite K₅-free graph with n?5 has at most 3n−9 edges. These bounds are also tight. We then use the bound on the number of edges in a K_3,3-free graph to extend two known NC algorithms for planar graphs to K_3,3-free graphs.     

Casual reasoning in planning1

Reasoning about actions necessarily involves tracking the truth of assertions about the world over time. The SIPE planning system retains the efficiency of the STRIPS assumption for this while enhancing expressive power by allowing the specification of a causl theory. Separation of knowledge about causality from knowledge about actions relieves operators of much of their representational burden and allows them to be applicable in a wide range of contexts. The implementation of causal theories is described, together with examples and evaluations of the system's expressive power and efficiency.     

Linearly many faults in Cayley graphs generated by transposition trees

We prove that when linearly many vertices are deleted in a Cayley graph generated by a transposition tree, the resulting graph has a large connected component containing almost all remaining vertices.     

An efficient parallel strategy for the perfect domination problem on distance-hereditary graphs

A graph is distance-hereditary if the distance stays the same between any of two vertices in every connected induced subgraph containing both. Two well-known classes of graphs, trees and cographs, both belong to distance-hereditary graphs. In this paper, we first show that the perfect domination problem can be solved in sequential linear-time on distance-hereditary graphs. By sketching some regular property of the problem, we also show that it can be easily parallelized on distance-hereditary graphs.     

Oriented colorings of 2-outerplanar graphs

A graph G is 2-outerplanar if it has a planar embedding such that the subgraph obtained by removing the vertices of the outer face is outerplanar. The oriented chromatic number of an oriented graph H is defined as the minimum order of an oriented graph H^′ such that H has a homomorphism to H^′. In this paper, we prove that 2-outerplanar graphs are 4-degenerate. We also show that oriented 2-outerplanar graphs have a homomorphism to the Paley tournament QR₆₇, which implies that their (strong) oriented chromatic number is at most 67.     

CoGCN: Combining co‐attention with graph convolutional network for entity linking with knowledge graphs

Entity linking is a fundamental task in natural language processing. The task of entity linking with knowledge graphs aims at linking mentions in text to their correct entities in a knowledge graph like DBpedia or YAGO2. Most of existing methods rely on hand‐designed features to model the contexts of mentions and entities, which are sparse and hard to calibrate. In this paper, we present a neural model that first combines co‐attention mechanism with graph convolutional network for entity linking with knowledge graphs, which extracts features of mentions and entities from their contexts automatically. Specifically, given the context of a mention and one of its candidate entities' context, we introduce the co‐attention mechanism to learn the relatedness between the mention context and the candidate entity context, and build the mention representation in consideration of such relatedness. Moreover, we propose a context‐aware graph convolutional network for entity representation, which takes both the graph structure of the candidate entity and its relatedness with the mention context into consideration. Experimental results show that our model consistently outperforms the baseline methods on five widely used datasets.     

一种新的基于递归分解的图可达性查询算法

针对现实中许多超大规模图可达性查询的问题,提出了一种新的基于递归分解的算法,即将原图递归分解成一系列生成树和剩余图两类子图,并通过分别查询这两类子图来减少查询开销.相比于区间标记、链分解、2-hop标签和路径树等传统算法,该算法不仅空间开销更小,且时间复杂度更低.仿真实验表明,该算法对处理大规模有向图可达性问题上存储规模更小且查询效率更高.     

图的点可区别边染色算法研究

针对一般图设计了一种新型的点可区别边染色算法。该算法把概率思想和图染色相结合, 根据点可区别边染色的约束规则确立目标函数, 利用交换规则逐步寻优, 当目标函数的值满足要求时染色成功。给出详细算法步骤并进行了测试和分析, 实验结果表明该算法可以求出满足猜想的点可区别边色数。     

我国宏观经济与证券市场关系的实证分析--基于名义 GDP 和上证指数发展速度的视角

宏观经济和证券市场的关系一直受到人们的关注,由于数据的选取和研究方法上的不同,导致宏观经济与证券市场的关系存在不同的结论或解释。从名义 GDP 和上证指数发展速度的视角,运用 HP 滤波以及 SVAR 等方法实证研究了宏观经济和证券市场的关系。研究发现：宏观经济和证券市场存在显著的因果关系;短期证券市场的波动是经济偶然性波动的预期,两者之间的滞后期效应与当期效应相互影响;方差分解表明宏观经济对于证券市场的长期贡献度很大。