Refutation of Spectral Graph Theory Conjectures with Search Algorithms)
원문 초록
We are interested in the automatic refutation of spectral graph theory conjectures. Most existing works address this problem either with the exhaustive generation of graphs with a limited size or with deep reinforcement learning. Exhaustive generation is limited by the size of the generated graphs and deep reinforcement learning takes hours or days to refute a conjecture. We propose to use search algorithms to address these shortcomings to find potentially large counter-examples to spectral graph theory conjectures in seconds. We apply a wide range of search algorithms to a selection of conjectures from Graffiti. Out of 13 already refuted conjectures from Graffiti, our algorithms are able to refute 12 in seconds. We also refute conjecture 197 from Graffiti which was open until now.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Reasoning on a Budget: Miniaturizing DeepSeek R1 with SFT-GRPO Alignment for Instruction-Tuned LLMs
Margin Trader: A Reinforcement Learning Framework for Portfolio Management with Margin and Constraints
Solving Dynamic Traveling Salesman Problems With Deep Reinforcement Learning
D3PG: Dirichlet DDPG for Task Partitioning and Offloading With Constrained Hybrid Action Space in Mobile-Edge Computing
Resource allocation algorithm for MEC based on Deep Reinforcement Learning
Task Independent Capsule-Based Agents for Deep Q-Learning
토론
이 논문과 연결된 포럼 글이 아직 없습니다.