Stable roommates spanner

DOI10.1016/J.COMGEO.2012.07.001MaRDI QIDQ691764zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, Paz Carmi, Lilach Chaitman-Yerushalmi, Sébastien Collette, Matthew J. Katz, Stefan Langerman

Publication date 4 December 2012

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2012.07.001

zbMATH Keywords

Yao graphgeometric spanners\(\Theta\)-graphstable roommates

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Signed and weighted graphs (05C22)

Recommendations

• Spanners with Slack
• Geometric stable roommates
• Sometimes Reliable Spanners of Almost Linear Size.
• Sometimes reliable spanners of almost linear size
• Multidimensional stable roommates with master list
• Light spanners
• Light spanners
• The Stable Roommates Problem with Ties
• Acyclic roommates

Cites work

• A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries
• Classes of graphs which approximate the complete Euclidean graph
• Dynamic Euclidean minimum spanning trees and extrema of binary functions
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• Geometric Spanner Networks
• Geometric stable roommates
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Yao Graphs Span Theta Graphs
• π/2-Angle Yao Graphs Are Spanners

Cited in

(4)

• Vertex fault-tolerant spanners for weighted points in polygonal domains
• Vertex Fault-Tolerant Geometric Spanners for Weighted Points
• Cone-based spanners of constant degree
• Locating battery charging stations to facilitate almost shortest paths

This page was built for publication: Stable roommates spanner

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