@article{brglez_li_stallmann_2005, title={On SAT instance classes and a method for reliable performance experiments with SAT solvers}, volume={43}, ISSN={["1573-7470"]}, DOI={10.1007/s10472-005-0417-5}, number={1-4}, journal={ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE}, author={Brglez, F and Li, XY and Stallmann, MF}, year={2005}, month={Jan}, pages={1–34} } @inbook{li_stallmann_brglez_2004, title={A Local search sat solver using an effective switching strategy and an efficient unit propagation}, volume={2919}, ISBN={3540208518}, booktitle={Theory and applications of satisfiability testing: 6th International Conference, SAT 2003, Santa Margherita Ligure, Italy, May 5-8, 2003, Selected revised papers}, publisher={Berlin; New York: Springer}, author={Li, X. Y. and Stallmann, M. F. and Brglez, F.}, year={2004}, pages={53–68} } @article{li_stallmann_2002, title={New bounds on the barycenter heuristic for bipartite graph drawing}, volume={82}, ISSN={["0020-0190"]}, DOI={10.1016/S0020-0190(01)00297-6}, abstractNote={The barycenter heuristic is often used to solve the NP-hard two-layer edge crossing minimization problem. It is well known that the barycenter heuristic can give solutions as bad as Ω(n) times the optimum, where n is the number of nodes in the graph. However, the example used in the proof has many isolated nodes. Mäkinen [EATCS Bull. 70 (2000) 156–158] conjectured that a better performance ratio is possible if isolated nodes are not present. We show that the performance ratio for the barycenter heuristic is still Ω(n) even for connected bipartite graphs. We also prove a tight constant ratio for the barycenter heuristic on bounded-degree graphs. The performance ratio is d−1, where d is the maximum degree of a node in the layer that can be permuted.}, number={6}, journal={INFORMATION PROCESSING LETTERS}, author={Li, XY and Stallmann, MF}, year={2002}, month={Jun}, pages={293–298} }