Connect four and graph decomposition

DOI10.1007/S00037-016-0123-1MaRDI QIDQ347118zbMATH OpenOpenAlexFDO

Authors Laurent Evain, Mathias Lederer, Bjarke Hammersholt Roune

Publication date 30 November 2016

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.4367

zbMATH Keywords

labeled graphspolynomial time complexitystandard sets

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Combinatorial identities, bijective combinatorics (05A19) Enumeration in graph theory (05C30) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Analysis of algorithms and problem complexity (68Q25)

Abstract: We introduce the standard decomposition, a 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, which implies that all Connect Four decompositions can be generated in polynomial time.

Recommendations

• Chain Decompositions of 4-Connected Graphs
• Quasi-4-Connected Components
• On \(P_4\)-decomposition of graphs
• scientific article; zbMATH DE number 2079338
• The decomposition of graphs into \(k\)-connected components

Cites work

• Components of Gröbner strata in the Hilbert scheme of points
• scientific article; zbMATH DE number 1375597 (Why is no real title available?)
• scientific article; zbMATH DE number 704831 (Why is no real title available?)
• La methode d'Horace pour l'interpolation à plusieurs variables
• On the postulation of \(s^d\) fat points in \(\mathbb P^d\)
• On vector partition functions
• The vanishing ideal of a finite set of closed points in affine space

This page was built for publication: Connect four and graph decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q347118)