Jump number of two-directional orthogonal ray graphs

DOI10.1007/978-3-642-20807-2_31zbMATH Open1341.05219OpenAlexW2152706MaRDI QIDQ3009778FDOQ3009778

Authors: José A. Soto, Claudio Telha 

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

Recommendations

• scientific article; zbMATH DE number 17532
• On the recognition of four-directional orthogonal ray graphs
• Jump number of dags having Dilworth number 2
• On the jump number problem in hereditary classes of bipartite graphs
• Computing maximum non-crossing matching in convex bipartite graphs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
• Grid intersection graphs and order dimension
• Title not available (Why is that?)
• Independent sets and hitting sets of bicolored rectangular families
• On the recognition of four-directional orthogonal ray graphs
• Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
• On orthogonal ray trees
• Fooling-sets and rank
• Matching colored points with rectangles

This page was built for publication: Jump number of two-directional orthogonal ray graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3009778)