|
Organizers |
A Boolean equation related to the arc number of a chord diagram
by
Yongwu Rong
George Washington University
This talk is motivated by recent work by Kouki Taniyama, who defined arc numbers for chord diagrams and characterized those chord diagrams whose arc number is two. We consider the problem of finding an efficient algorithm to determine the arc number of a given chord diagram. We show that this problem can be reduced of the problem of finding the size of a minimal solution of a special kind of Boolean equation where no negation appears in its standard conjunctive normal form. While the later problem in general can be shown to be NP-hard, the computational complexity for computing the arc number may still be easier since the Boolean equations coming from chord diagrams may be rather special.
Date received: February 26, 2009
Copyright © 2009 by the author(s). The author(s) of this work and the organizers of the conference have granted their consent to include this abstract in Topology Atlas. Document # cayk-14.