Connect Four and Graph Decomposition

详细信息    查看全文

• 作者：Laurent Evain ; Mathias Lederer ; Bjarke Hammersholt Roune
• 关键词：Subject classification05A17 ; 05A19 ; 05C30 ; 05C78 ; 68Q25
• 刊名：Computational Complexity
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：25
• 期：4
• 页码：815-848
• 全文大小：835 KB
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity
  Computational Mathematics and Numerical Analysis
  
• 出版者：Birkh盲user Basel
• ISSN：1420-8954
• 卷排序：25

文摘

We introduce standard decomposition, a natural way of decomposing a labeled graph into a sum of certain labeled subgraphs. We motivate this graph-theoretic concept by relating it to Connect Four decompositions of standard sets. We prove that all standard decompositions can be generated in polynomial time as a function of the combined size of the input and the output. This implies that all Connect Four decompositions can be generated in polynomial time.