The cutwidth problem fora graph G is to embed G into a path such thatthe maximum number of overlap edges is minimized.This paperpresents an approach based on the degree se- quence of G for determining the exact valu...The cutwidth problem fora graph G is to embed G into a path such thatthe maximum number of overlap edges is minimized.This paperpresents an approach based on the degree se- quence of G for determining the exact value of cutwidth of typical graphs (e.g.,n- cube,cater- pillars) .Relations between the cutwidth and other graph- theoretic parameters are studied as wel展开更多
The problem studied in this paper is to determine E(p,C),the maximum size of a connected graph G with the given vertex number p and cutwidth C. This paper presents some results on this problem.
The cutwidth problem for a graph G is to embed G into a path P n such that the maximum number of overlap edges (i.e., the congestion) is minimized. It is known that the problem for general graphs is NP-hard while it ...The cutwidth problem for a graph G is to embed G into a path P n such that the maximum number of overlap edges (i.e., the congestion) is minimized. It is known that the problem for general graphs is NP-hard while it is polynomially solvable for trees. This paper presents an exact formula for the cutwidth of trees with diameter at most 4. A relation with the bandwidth is discussed as well.展开更多
The cutwidth of a graph G is the minimum number of overlap edges when G is embedded into a path Pn.The cutwidth problem for a graph G is to determine the cutwidth of G.A graph G with cutwidth k is k-cutwidth critical ...The cutwidth of a graph G is the minimum number of overlap edges when G is embedded into a path Pn.The cutwidth problem for a graph G is to determine the cutwidth of G.A graph G with cutwidth k is k-cutwidth critical if every proper subgraph of G has cutwidth less than k and G is homeomorphically minimal.In this paper,we completely investigated methods of forming a k-cutwidth(k>1)critical tree T.展开更多
In 2009, Kwong and Lee considered a new labeling problem of graph theory–the edge-balance index set of graph. In this paper, we investigated the edge-balanced properties of product of paths by using a method known as...In 2009, Kwong and Lee considered a new labeling problem of graph theory–the edge-balance index set of graph. In this paper, we investigated the edge-balanced properties of product of paths by using a method known as embedding labeling graph method.展开更多
Let G=(V,E)be a graph.For a vertex labeling f:V→Z2,it induces an edge labeling f+:E→Z2,where for each edge v1 v2∈E we have f+(v1 v2)=f(v1)+f(v2).For each i∈Z2,we use vf(i)(respectively,ef(i))to denote the number o...Let G=(V,E)be a graph.For a vertex labeling f:V→Z2,it induces an edge labeling f+:E→Z2,where for each edge v1 v2∈E we have f+(v1 v2)=f(v1)+f(v2).For each i∈Z2,we use vf(i)(respectively,ef(i))to denote the number of vertices(respectively,edges)with label i.A vertex labeling f of G is said to be friendly if vertices with different labels differ in size by at most one.The full friendly index set of a graph G,denoted by F F I(G),consists of all possible values of ef(1)-ef(0),where f ranges over all friendly labelings of G.In this paper,motivated by a problem raised by[6],we study the full friendly index sets of a family of cubic graphs.展开更多
为进一步优化重叠社区检测算法,提出了一种新的基于度和节点聚类系数的节点重要性定义,按照节点重要性降序更新节点,固定节点更新策略,提高社区检测的稳定性。在此基础上,提出了一种基于图嵌入和多标签传播的重叠社区检测算法(overlappi...为进一步优化重叠社区检测算法,提出了一种新的基于度和节点聚类系数的节点重要性定义,按照节点重要性降序更新节点,固定节点更新策略,提高社区检测的稳定性。在此基础上,提出了一种基于图嵌入和多标签传播的重叠社区检测算法(overlapping community detection based on graph embedding and multi-label propagation algorithm,OCD-GEMPA)。该算法结合node2vec模型对节点进行低维向量表示,构建节点之间的权重值矩阵,根据权重值计算标签归属系数,据此选择标签,避免了随机选择问题。在真实数据集和人工合成数据集上对该算法进行实验验证。实验结果表明,与其他重叠社区检测算法相比,OCD-GEMPA在EQ和NMI这两个指标都有明显提升,具有更好的准确性和稳定性。展开更多
Event detection(ED)seeks to recognize event triggers and classify them into the predefined event types.Chinese ED is formulated as a character-level task owing to the uncertain word boundaries.Prior methods try to inc...Event detection(ED)seeks to recognize event triggers and classify them into the predefined event types.Chinese ED is formulated as a character-level task owing to the uncertain word boundaries.Prior methods try to incorpo-rate word-level information into characters to enhance their semantics.However,they experience two problems.First,they fail to incorporate word-level information into each character the word encompasses,causing the insufficient word-charac-ter interaction problem.Second,they struggle to distinguish events of similar types with limited annotated instances,which is called the event confusing problem.This paper proposes a novel model named Label-Aware Heterogeneous Graph Attention Network(L-HGAT)to address these two problems.Specifically,we first build a heterogeneous graph of two node types and three edge types to maximally preserve word-character interactions,and then deploy a heterogeneous graph attention network to enhance the semantic propagation between characters and words.Furthermore,we design a pushing-away game to enlarge the predicting gap between the ground-truth event type and its confusing counterpart for each character.Experimental results show that our L-HGAT model consistently achieves superior performance over prior competitive methods.展开更多
基金Supported by the National Natural Science Foundation of China (1 0 0 71 0 76 )
文摘The cutwidth problem fora graph G is to embed G into a path such thatthe maximum number of overlap edges is minimized.This paperpresents an approach based on the degree se- quence of G for determining the exact value of cutwidth of typical graphs (e.g.,n- cube,cater- pillars) .Relations between the cutwidth and other graph- theoretic parameters are studied as wel
基金Supported by Natural Science Foundation of Zhejiang Province(1 0 2 0 5 5 )
文摘The problem studied in this paper is to determine E(p,C),the maximum size of a connected graph G with the given vertex number p and cutwidth C. This paper presents some results on this problem.
基金Supported by the National Natural Science Foundation of China( 1 0 0 71 0 76)
文摘The cutwidth problem for a graph G is to embed G into a path P n such that the maximum number of overlap edges (i.e., the congestion) is minimized. It is known that the problem for general graphs is NP-hard while it is polynomially solvable for trees. This paper presents an exact formula for the cutwidth of trees with diameter at most 4. A relation with the bandwidth is discussed as well.
基金Supported by Soft Science Foundation of Henan Province(Grant No.192400410212)the Science and Technology Key Project of Henan Province of China(Grant No.22210211008)。
文摘The cutwidth of a graph G is the minimum number of overlap edges when G is embedded into a path Pn.The cutwidth problem for a graph G is to determine the cutwidth of G.A graph G with cutwidth k is k-cutwidth critical if every proper subgraph of G has cutwidth less than k and G is homeomorphically minimal.In this paper,we completely investigated methods of forming a k-cutwidth(k>1)critical tree T.
文摘In 2009, Kwong and Lee considered a new labeling problem of graph theory–the edge-balance index set of graph. In this paper, we investigated the edge-balanced properties of product of paths by using a method known as embedding labeling graph method.
基金Supported by the National Natural Science Foundation of China(Grant No.11801149)Doctoral Fund of Henan Polytechnic University(Grant No.B2018-55)。
文摘Let G=(V,E)be a graph.For a vertex labeling f:V→Z2,it induces an edge labeling f+:E→Z2,where for each edge v1 v2∈E we have f+(v1 v2)=f(v1)+f(v2).For each i∈Z2,we use vf(i)(respectively,ef(i))to denote the number of vertices(respectively,edges)with label i.A vertex labeling f of G is said to be friendly if vertices with different labels differ in size by at most one.The full friendly index set of a graph G,denoted by F F I(G),consists of all possible values of ef(1)-ef(0),where f ranges over all friendly labelings of G.In this paper,motivated by a problem raised by[6],we study the full friendly index sets of a family of cubic graphs.
文摘为进一步优化重叠社区检测算法,提出了一种新的基于度和节点聚类系数的节点重要性定义,按照节点重要性降序更新节点,固定节点更新策略,提高社区检测的稳定性。在此基础上,提出了一种基于图嵌入和多标签传播的重叠社区检测算法(overlapping community detection based on graph embedding and multi-label propagation algorithm,OCD-GEMPA)。该算法结合node2vec模型对节点进行低维向量表示,构建节点之间的权重值矩阵,根据权重值计算标签归属系数,据此选择标签,避免了随机选择问题。在真实数据集和人工合成数据集上对该算法进行实验验证。实验结果表明,与其他重叠社区检测算法相比,OCD-GEMPA在EQ和NMI这两个指标都有明显提升,具有更好的准确性和稳定性。
基金The project is supported by the Natural Science Foundation of Henan Province(No.082300460190)the Program for Science and Technology Innovation Talents in Universities of Henan Province(No. 2010HASTIT043)
基金This work was supported by the National Key Research and Development Program of China under Grant No.2021YFB3100600the Youth Innovation Promotion Association of Chinese Academy of Sciences under Grant No.2021153the State Key Program of National Natural Science Foundation of China under Grant No.U2336202.
文摘Event detection(ED)seeks to recognize event triggers and classify them into the predefined event types.Chinese ED is formulated as a character-level task owing to the uncertain word boundaries.Prior methods try to incorpo-rate word-level information into characters to enhance their semantics.However,they experience two problems.First,they fail to incorporate word-level information into each character the word encompasses,causing the insufficient word-charac-ter interaction problem.Second,they struggle to distinguish events of similar types with limited annotated instances,which is called the event confusing problem.This paper proposes a novel model named Label-Aware Heterogeneous Graph Attention Network(L-HGAT)to address these two problems.Specifically,we first build a heterogeneous graph of two node types and three edge types to maximally preserve word-character interactions,and then deploy a heterogeneous graph attention network to enhance the semantic propagation between characters and words.Furthermore,we design a pushing-away game to enlarge the predicting gap between the ground-truth event type and its confusing counterpart for each character.Experimental results show that our L-HGAT model consistently achieves superior performance over prior competitive methods.
