TY - GEN

T1 - Jump number of two-directional orthogonal ray graphs

AU - Soto, José A.

AU - Telha, Claudio

PY - 2011

Y1 - 2011

N2 - We model maximum cross-free matchings and minimum biclique covers of two-directional orthogonal ray graphs (2-dorgs ) as maximum independent sets and minimum hitting sets of an associated family of rectangles in the plane, respectively. We then compute the corresponding maximum independent set using linear programming and uncrossing techniques. This procedure motivates an efficient combinatorial algorithm to find a cross-free matching and a biclique cover of the same cardinality, proving the corresponding min-max relation. We connect this min-max relation with the work of Györi, [19] Lubiw [23], and Frank and Jordán [16] on seemingly unrelated problems. Our result can be seen as a non-trivial application of Frank and Jordán's Theorem. As a direct consequence, we obtain the first polynomial algorithm for the jump number problem on 2-dorgs. For the subclass of convex graphs, our approach is a vast improvement over previous algorithms. Additionally, we prove that the weighted maximum cross-free matching problem is NP-complete for 2-dorgs and give polynomial algorithms for some subclasses.

AB - We model maximum cross-free matchings and minimum biclique covers of two-directional orthogonal ray graphs (2-dorgs ) as maximum independent sets and minimum hitting sets of an associated family of rectangles in the plane, respectively. We then compute the corresponding maximum independent set using linear programming and uncrossing techniques. This procedure motivates an efficient combinatorial algorithm to find a cross-free matching and a biclique cover of the same cardinality, proving the corresponding min-max relation. We connect this min-max relation with the work of Györi, [19] Lubiw [23], and Frank and Jordán [16] on seemingly unrelated problems. Our result can be seen as a non-trivial application of Frank and Jordán's Theorem. As a direct consequence, we obtain the first polynomial algorithm for the jump number problem on 2-dorgs. For the subclass of convex graphs, our approach is a vast improvement over previous algorithms. Additionally, we prove that the weighted maximum cross-free matching problem is NP-complete for 2-dorgs and give polynomial algorithms for some subclasses.

KW - Combination optimization

KW - Linear programming

UR - http://www.scopus.com/inward/record.url?scp=79959949982&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-20807-2_31

DO - 10.1007/978-3-642-20807-2_31

M3 - Conference contribution

AN - SCOPUS:79959949982

SN - 9783642208065

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 389

EP - 403

BT - Integer Programming and Combinatoral Optimization - 15th International Conference, IPCO 2011, Proceedings

Y2 - 15 June 2011 through 17 June 2011

ER -