报告人：何萌，达尔豪斯大学
报告地点：计算机楼313
报告时间：2025年7月7日10:30-11:30
报告题目：区间图的最优距离标注
个人简介：
何萌，加拿大达尔豪斯大学（Dalhousie University）计算机科学网络赌博网站
教授。于2008年在加拿大滑铁卢大学（University of Waterloo）计算机科学网络赌博网站
获得博士学位。在加入达尔豪斯大学之前，曾在卡尔顿大学（Carleton University）和滑铁卢大学从事博士后和研究工作。
研究方向涵盖算法、数据结构与计算几何，并致力于这些理论在数据库效率优化、文本检索、生物信息学及地理信息系统等领域的应用。何萌教授于CCCG、SoCG、WAOA等国际学术会议发表论文10余篇，并指导荣誉学位论文及加拿大本科生研究奖（USRA）项目。
报告简介：
本次报告内容为一种针对区间图的新型距离标签方案。该方案在保证恒定查询时间的前提下，将每个顶点的存储开销优化至最多
比特。相较于Gavoille和Paul提出的连通区间图标签方案，其需每个顶点比特且保持恒定查询时间，本方案显著降低了空间成本。特别值得注意的是，改进后的空间复杂度与Gavoille和Paul证明的理论下界仅相差低阶项，因此具有最优性。基于此方案，我们进一步设计了适用于圆弧图的比特距离标签方案，在保持恒定查询时间的同时，将Gavoille和Paul原有方案的比特存储需求降低了近40%。此外，针对弦图我们提出了比特的距离标签方案，可在时间内响应距离查询。目前已知的理论下界为比特，本方案在现有理论限制下实现了显著的存储效率提升。
