Jump number of two-directional orthogonal ray graphs

José A. Soto, Claudio Telha

Resultado de la investigación: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

19 Citas (Scopus)

Resumen

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.
Idioma originalInglés
Título de la publicación alojadaInteger Programming and Combinatoral Optimization - 15th International Conference, IPCO 2011, Proceedings
Páginas389-403
Número de páginas15
DOI
EstadoPublicada - 2011
Evento15th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2011 - New York, NY, Estados Unidos
Duración: 15 jun. 201117 jun. 2011

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen6655 LNCS
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349

Conferencia

Conferencia15th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2011
País/TerritorioEstados Unidos
CiudadNew York, NY
Período15/06/1117/06/11

Palabras clave

  • Combination optimization
  • Linear programming

Huella

Profundice en los temas de investigación de 'Jump number of two-directional orthogonal ray graphs'. En conjunto forman una huella única.

Citar esto