bipartization
Jump to navigation
Jump to search
English[edit]
Noun[edit]
bipartization (plural bipartizations)
- (mathematics) The removal of vertices from a graph in order to make it bipartite
- 2015, Piotr Gnaciński, Monika Rosicka, Ravishankar Ramanathan, Karol Horodecki, Michał Horodecki, Paweł Horodecki, Simone Severini, “Linear game non-contextuality and Bell inequalities - a graph-theoretic approach”, in arXiv[1]:
- We relate the problem of computing the classical value of single-party anti-correlation XOR games to finding the edge bipartization number of a graph, which is known to be MaxSNP hard, and connect the computation of the classical value of more general XOR-d games to the identification of specific cycles in the graph.