Jump number of two-directional orthogonal ray graphs

DOI10.1007/978-3-642-20807-2_31MaRDI QIDQ3009778zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

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

Cites work

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

Cited in

(9)

• 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
• On the recognition of four-directional orthogonal ray graphs
• Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
• scientific article; zbMATH DE number 17532 (Why is no real title available?)
• Matching colored points with rectangles
• Grid intersection graphs and order dimension
• On orthogonal ray trees

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)