带条形扩展的图形类上的常数圆圆分布支配 (Constant round distributed domination on graph classes with bounded expansion) - 专知论文

会员服务 ·

0

图 · 类别 · 分解的 · DC · 近似 ·

2021 年 6 月 28 日

Constant round distributed domination on graph classes with bounded expansion

翻译：带条形扩展的图形类上的常数圆圆分布支配

Simeon Kublenz,Sebastian Siebertz,Alexandre Vigny

from arxiv, Paper accepted at SIROCCO 2021, implemented reviews, corrected an error in Lemma 1

We show that the dominating set problem admits a constant factor approximation in a constant number of rounds in the LOCAL model of distributed computing on graph classes with bounded expansion. This generalizes a result of Czygrinow et al. for graphs with excluded topological minors.

翻译：我们显示,占支配地位的既定问题在LOCAL模式中,在图表类分布式计算模式中,在连续数轮中以固定的系数近似值为恒定值,这种分布式计算模式具有边际扩张,它概括了Czygrinow等人对被排除在外的表层未成年人的图表的结果。

0

相关内容

最新《图神经网络知识图谱补全综述论文》A Survey on Graph Neural Networks for Knowledge Graph Completion

最新《图神经网络知识图谱补全综述论文》A Survey on Graph Neural Networks for Knowledge Graph Completion

专知会员服务

134+阅读 · 2020年7月29日

【KDD2020-清华大学】自适应图编码器，Adaptive Graph Encoder for Attributed Graph Embedding

【KDD2020-清华大学】自适应图编码器，Adaptive Graph Encoder for Attributed Graph Embedding

专知会员服务

98+阅读 · 2020年7月6日

【NLP模型压缩方法综述】《A Survey of Methods for Model Compression in NLP》by Madison May

【NLP模型压缩方法综述】《A Survey of Methods for Model Compression in NLP》by Madison May

专知会员服务

42+阅读 · 2020年4月22日

因果图，Causal Graphs，52页ppt

因果图，Causal Graphs，52页ppt

专知会员服务

241+阅读 · 2020年4月19日

【异构图迁移的零样本学习】Heterogeneous Graph-based Knowledge Transfer for Generalized Zero-shot Learning

【异构图迁移的零样本学习】Heterogeneous Graph-based Knowledge Transfer for Generalized Zero-shot Learning

专知会员服务

64+阅读 · 2020年4月17日

图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》

图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》

专知会员服务

92+阅读 · 2020年3月12日

【WWW2020-香港中文大学】MAGNN:异构图嵌入的集合图神经网络

【WWW2020-香港中文大学】MAGNN:异构图嵌入的集合图神经网络

专知会员服务

111+阅读 · 2020年2月13日

【WWW2020-MAGNN】异质图嵌入的集合图神经网络 MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding

【WWW2020-MAGNN】异质图嵌入的集合图神经网络 MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding

专知会员服务

115+阅读 · 2020年2月10日

【文献综述】分布式机器学习综述论文，33页pdf，A Survey on Distributed Machine Learning

【文献综述】分布式机器学习综述论文，33页pdf，A Survey on Distributed Machine Learning

专知会员服务

120+阅读 · 2019年12月23日

Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation

Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation

专知会员服务

54+阅读 · 2019年10月17日

局部学习的特征选择：Local-Learning-Based Feature Selection

局部学习的特征选择：Local-Learning-Based Feature Selection

我爱读PAMI

14+阅读 · 2019年9月20日

Graph Neural Network（GNN）最全资源整理分享

Graph Neural Network（GNN）最全资源整理分享

深度学习与NLP

339+阅读 · 2019年7月9日

Hierarchically Structured Meta-learning

Hierarchically Structured Meta-learning

CreateAMind

23+阅读 · 2019年5月22日

Ray RLlib: Scalable 降龙十八掌

Ray RLlib: Scalable 降龙十八掌

CreateAMind

8+阅读 · 2018年12月28日

计算机类 | LICS 2019等国际会议信息7条

计算机类 | LICS 2019等国际会议信息7条

Call4Papers

3+阅读 · 2018年12月17日

Disentangled的假设的探讨

Disentangled的假设的探讨

CreateAMind

9+阅读 · 2018年12月10日

disentangled-representation-papers

disentangled-representation-papers

CreateAMind

26+阅读 · 2018年9月12日

Hierarchical Disentangled Representations

Hierarchical Disentangled Representations

CreateAMind

4+阅读 · 2018年4月15日

【论文推荐】最新5篇度量学习（Metric Learning）相关论文—人脸验证、BIER、自适应图卷积、注意力机制、单次学习

【论文推荐】最新5篇度量学习（Metric Learning）相关论文—人脸验证、BIER、自适应图卷积、注意力机制、单次学习

专知

17+阅读 · 2018年2月11日

carla 学习笔记

carla 学习笔记

CreateAMind

9+阅读 · 2018年2月7日

Exact Distance Oracles for Planar Graphs with Failing Vertices

Arxiv

0+阅读 · 2021年8月30日

Trims and Extensions of Quadratic APN Functions

Arxiv

0+阅读 · 2021年8月30日

The volume-of-tube method for Gaussian random fields with inhomogeneous variance

Arxiv

0+阅读 · 2021年8月30日

Exact algorithms for maximum weighted independent set on sparse graphs

Arxiv

0+阅读 · 2021年8月29日

Bayesian Non-parametric Quantile Process Regression and Estimation of Marginal Quantile Effects

Arxiv

0+阅读 · 2021年8月29日

Estimation of Riemannian distances between covariance operators and Gaussian processes

Estimation of Riemannian distances between covariance operators and Gaussian processes

Arxiv

1+阅读 · 2021年8月26日

Distributed Soft Bayesian Additive Regression Trees

Arxiv

0+阅读 · 2021年8月26日

Deep Ritz method for the spectral fractional Laplacian equation using the Caffarelli-Silvestre extension

Arxiv

0+阅读 · 2021年8月26日

Distributed Graph Convolutional Networks

Arxiv

19+阅读 · 2020年7月13日

Optimal Algorithms for Non-Smooth Distributed Optimization in Networks

Arxiv

7+阅读 · 2018年6月1日

VIP会员

文章信息

相关主题

相关VIP内容

最新《图神经网络知识图谱补全综述论文》A Survey on Graph Neural Networks for Knowledge Graph Completion

最新《图神经网络知识图谱补全综述论文》A Survey on Graph Neural Networks for Knowledge Graph Completion

专知会员服务

134+阅读 · 2020年7月29日

【KDD2020-清华大学】自适应图编码器，Adaptive Graph Encoder for Attributed Graph Embedding

【KDD2020-清华大学】自适应图编码器，Adaptive Graph Encoder for Attributed Graph Embedding

专知会员服务

98+阅读 · 2020年7月6日

【NLP模型压缩方法综述】《A Survey of Methods for Model Compression in NLP》by Madison May

【NLP模型压缩方法综述】《A Survey of Methods for Model Compression in NLP》by Madison May

专知会员服务

42+阅读 · 2020年4月22日

因果图，Causal Graphs，52页ppt

因果图，Causal Graphs，52页ppt

专知会员服务

241+阅读 · 2020年4月19日

【异构图迁移的零样本学习】Heterogeneous Graph-based Knowledge Transfer for Generalized Zero-shot Learning

【异构图迁移的零样本学习】Heterogeneous Graph-based Knowledge Transfer for Generalized Zero-shot Learning

专知会员服务

64+阅读 · 2020年4月17日

图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》

图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》

专知会员服务

92+阅读 · 2020年3月12日

【WWW2020-香港中文大学】MAGNN:异构图嵌入的集合图神经网络

【WWW2020-香港中文大学】MAGNN:异构图嵌入的集合图神经网络

专知会员服务

111+阅读 · 2020年2月13日

【WWW2020-MAGNN】异质图嵌入的集合图神经网络 MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding

【WWW2020-MAGNN】异质图嵌入的集合图神经网络 MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding

专知会员服务

115+阅读 · 2020年2月10日

【文献综述】分布式机器学习综述论文，33页pdf，A Survey on Distributed Machine Learning

【文献综述】分布式机器学习综述论文，33页pdf，A Survey on Distributed Machine Learning

专知会员服务

120+阅读 · 2019年12月23日

Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation

Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation

专知会员服务

54+阅读 · 2019年10月17日

热门VIP内容

相关资讯

局部学习的特征选择：Local-Learning-Based Feature Selection

局部学习的特征选择：Local-Learning-Based Feature Selection

我爱读PAMI

14+阅读 · 2019年9月20日

Graph Neural Network（GNN）最全资源整理分享

Graph Neural Network（GNN）最全资源整理分享

深度学习与NLP

339+阅读 · 2019年7月9日

Hierarchically Structured Meta-learning

Hierarchically Structured Meta-learning

CreateAMind

23+阅读 · 2019年5月22日

Ray RLlib: Scalable 降龙十八掌

Ray RLlib: Scalable 降龙十八掌

CreateAMind

8+阅读 · 2018年12月28日

计算机类 | LICS 2019等国际会议信息7条

计算机类 | LICS 2019等国际会议信息7条

Call4Papers

3+阅读 · 2018年12月17日

Disentangled的假设的探讨

Disentangled的假设的探讨

CreateAMind

9+阅读 · 2018年12月10日

disentangled-representation-papers

disentangled-representation-papers

CreateAMind

26+阅读 · 2018年9月12日

Hierarchical Disentangled Representations

Hierarchical Disentangled Representations

CreateAMind

4+阅读 · 2018年4月15日

【论文推荐】最新5篇度量学习（Metric Learning）相关论文—人脸验证、BIER、自适应图卷积、注意力机制、单次学习

【论文推荐】最新5篇度量学习（Metric Learning）相关论文—人脸验证、BIER、自适应图卷积、注意力机制、单次学习

专知

17+阅读 · 2018年2月11日

carla 学习笔记

carla 学习笔记

CreateAMind

9+阅读 · 2018年2月7日

相关论文

Exact Distance Oracles for Planar Graphs with Failing Vertices

Arxiv

0+阅读 · 2021年8月30日

Trims and Extensions of Quadratic APN Functions

Arxiv

0+阅读 · 2021年8月30日

The volume-of-tube method for Gaussian random fields with inhomogeneous variance

Arxiv

0+阅读 · 2021年8月30日

Exact algorithms for maximum weighted independent set on sparse graphs

Arxiv

0+阅读 · 2021年8月29日

Bayesian Non-parametric Quantile Process Regression and Estimation of Marginal Quantile Effects

Arxiv

0+阅读 · 2021年8月29日

Estimation of Riemannian distances between covariance operators and Gaussian processes

Estimation of Riemannian distances between covariance operators and Gaussian processes

Arxiv

1+阅读 · 2021年8月26日

Distributed Soft Bayesian Additive Regression Trees

Arxiv

0+阅读 · 2021年8月26日

Deep Ritz method for the spectral fractional Laplacian equation using the Caffarelli-Silvestre extension

Arxiv

0+阅读 · 2021年8月26日

Distributed Graph Convolutional Networks

Arxiv

19+阅读 · 2020年7月13日

Optimal Algorithms for Non-Smooth Distributed Optimization in Networks

Arxiv

7+阅读 · 2018年6月1日

微信扫码咨询专知VIP会员