期刊文献+
共找到4篇文章
< 1 >
每页显示 20 50 100
Parallel Bounded Search for the Maximum Clique Problem
1
作者 江华 白珂 +3 位作者 刘海姣 李初民 Felip Manya 付樟华 《Journal of Computer Science & Technology》 SCIE EI CSCD 2023年第5期1187-1202,共16页
Given an undirected graph,the Maximum Clique Problem(MCP)is to find a largest complete subgraph of the graph.MCP is NP-hard and has found many practical applications.In this paper,we propose a parallel Branch-and-Boun... Given an undirected graph,the Maximum Clique Problem(MCP)is to find a largest complete subgraph of the graph.MCP is NP-hard and has found many practical applications.In this paper,we propose a parallel Branch-and-Bound(BnB)algorithm to tackle this NP-hard problem,which carries out multiple bounded searches in parallel.Each search has its upper bound and shares a lower bound with the rest of the searches.The potential benefit of the proposed approach is that an active search terminates as soon as the best lower bound found so far reaches or exceeds its upper bound.We describe the implementation of our highly scalable and efficient parallel MCP algorithm,called PBS,which is based on a state-of-the-art sequential MCP algorithm.The proposed algorithm PBS is evaluated on hard DIMACS and BHOSLIB instances.The results show that PBS achieves a near-linear speedup on most DIMACS instances and a superlinear speedup on most BHOSLIB instances.Finally,we give a detailed analysis that explains the good speedups achieved for the tested instances. 展开更多
关键词 Branch-and-Bound(BnB) maximum clique problem(MCP) parallel search
原文传递
Maximum Cliques of Hypergraphs and Polynomial Optimization 被引量:1
2
作者 Yan-ming CHANG Yue-jian PENG 《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 2018年第4期842-855,共14页
A remarkable connection between the clique number and the Lagrangian of a graph was established by Motzkin and Straus. Later, Rota Bul′o and Pelillo extended the theorem of Motzkin-Straus to r-uniform hypergraphs by ... A remarkable connection between the clique number and the Lagrangian of a graph was established by Motzkin and Straus. Later, Rota Bul′o and Pelillo extended the theorem of Motzkin-Straus to r-uniform hypergraphs by studying the relation of local(global) minimizers of a homogeneous polynomial function of degree r and the maximal(maximum) cliques of an r-uniform hypergraph. In this paper, we study polynomial optimization problems for non-uniform hypergraphs with four different types of edges and apply it to get an upper bound of Tur′an densities of complete non-uniform hypergraphs. 展开更多
关键词 HYPERGRAPH maximum clique polynomial optimization
原文传递
Maximum Independent Sets and Supervised Learning 被引量:1
3
作者 Roberto Montemanni Derek H.Smith Xiao-Chen Chou 《Journal of the Operations Research Society of China》 EI CSCD 2023年第4期957-972,共16页
The paper discusses an enhancement to a recently presented supervised learning algorithm to solve the Maximum Independent Set problem.In particular,it is shown that the algorithm can be improved by simplifying the tas... The paper discusses an enhancement to a recently presented supervised learning algorithm to solve the Maximum Independent Set problem.In particular,it is shown that the algorithm can be improved by simplifying the task learnt by the neural network adopted,with measurable effects on the quality of the solutions provided on unseen instances.Empirical results are presented to validate the idea.. 展开更多
关键词 maximum clique problem maximum Independent Set problem Machine learning Graph theory
原文传递
Connection Between Continuous Optimization and Turán Densities of Non-uniform Hypergraphs
4
作者 Xiao-bing GUO Yue-jian PENG 《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 2021年第4期858-866,共9页
A classical result of Motzkin and Straus established the connection between the Lagrangian of a graph and its maximum cliques.Applying it,they gave a new proof of Turán’s theorem.This aroused the interests in st... A classical result of Motzkin and Straus established the connection between the Lagrangian of a graph and its maximum cliques.Applying it,they gave a new proof of Turán’s theorem.This aroused the interests in studying the connection between continuous optimization and extremal problems in combinatorics.In 2009,S.Rota Bulòand M.Pelillo extended the result of Motzkin-Straus to r-uniform hypergraphs.Recently,Johnston and Lu initiated the study of the Turán density of a non-uniform hypergraph.Polynomial optimization problems related to several types of non-uniform hypergraphs and its applications on Turán densities have also been studied.In this paper,we obtain a Motzkin-Straus type of results for all non-uniform hypergraphs.Applying it,we give an upper bound of the Turán density of a complete non-uniform hypergraph. 展开更多
关键词 hypergrapli maximum clique polynomial optimization
原文传递
上一页 1 下一页 到第
使用帮助 返回顶部