We study the imbalance problem on complete bipartite graphs. The imbalance problem is a graph layout problem and is known to be NP-complete. Graph layout problems find their applications in the optimization of networks for parallel computer architectures, VLSI circuit design, information retrieval, numerical analysis, computational biology, graph theory, scheduling and archaeology. In this paper, we give characterizations for the optimal solutions of the imbalance problem on complete bipartite graphs. Using the characterizations, we can solve the imbalance problem in $\mathcal{O}(\log(|V|) \cdot \log(\log(|V|)))$ time, when given the cardinalities of the parts of the graph, and verify whether a given solution is optimal in $O(|V|)$ time on complete bipartite graphs. We also introduce a restricted form of proper interval bipartite graphs on which the imbalance problem is solvable in $\mathcal{O}(c \cdot \log(|V|) \cdot \log(\log(|V|)))$ time, where $c = \mathcal{O}(|V|)$, by using the aforementioned characterizations.


翻译:我们研究了完整的双部分图形中的不平衡问题。 不平衡问题是一个图表布局问题, 已知是NP- 完整的。 图表布局问题在同步计算机结构网络优化、 VLSI 电路设计、 信息检索、 数字分析、 计算生物学、 图形理论、 排期和考古学中找到了它们的应用。 在本文中, 我们给完整的双部分图形中的不平衡问题的最佳解决方案定性。 使用这些特征, 我们可以解决$\ mathcal{ O} (\\ log( ⁇ V)\ dot\ log ( log)\ log ( log( ⁇ ) ) $( ⁇ ) = log_\ log\ log_ ) 的不平衡问题, 并核查一个给定的解决方案是否在 $O( ) 美元( v) / log\ / log= 美元( log=) 时间( $\\\ log\ ) \\\\\\\\\\\\ \\\\ \\ \\\\\\\ \ \\\ \ \\ \\\\\\ \ \ \\\ \\\\\\\\\\\\\\\\\\ \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ \\\\\\\\\\ \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

0
下载
关闭预览

相关内容

Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
110+阅读 · 2020年5月15日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
7+阅读 · 2020年6月29日
SepNE: Bringing Separability to Network Embedding
Arxiv
3+阅读 · 2019年2月26日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关VIP内容
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
110+阅读 · 2020年5月15日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
相关资讯
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员