Jump Number of Two-Directional Orthogonal Ray Graphs

DOI10.1007/978-3-642-20807-2_31zbMath1341.05219OpenAlexW2152706MaRDI QIDQ3009778

Claudio Telha, Jose A. Soto

Publication date: 24 June 2011

Published in: Integer Programming and Combinatoral Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20807-2_31

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (9)

Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve ⋮ On orthogonal ray trees ⋮ Matching colored points with rectangles ⋮ Approximating minimum Manhattan networks in higher dimensions ⋮ Recognition and drawing of stick graphs ⋮ Grid intersection graphs and order dimension ⋮ Independent sets and hitting sets of bicolored rectangular families ⋮ Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity ⋮ Fooling-sets and rank

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On orthogonal ray graphs
• A minimax theorem on intervals
• An algorithm to increase the node-connectivity of a digraph by one
• A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders
• Optimal packing and covering in the plane are NP-complete
• A weighted min-max relation for intervals
• A mathematical analysis of human leukocyte antigen serology
• Finding minimum generators of path systems
• Alternating cycle-free matchings
• A weighted version of the jump number problem on two-dimensional orders is NP-complete
• Pushdown-reduce: An algorithm for connectivity augmentation and poset covering problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Minimal edge-coverings of pairs of sets
• On edge perfectness and classes of bipartite graphs
• Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
• An algorithm for covering polygons with rectangles
• Graph Classes: A Survey
• Covering Regions by Rectangles
• Communication Complexity
• Irredundant intervals
• Algorithms – ESA 2004
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Jump Number of Two-Directional Orthogonal Ray Graphs