Complexity of graph evolutions

Gao, Jeffrey; Kainen, Paul C.

数学 > 组合数学

arXiv:2412.00212 (math)

[提交于 2024年11月29日 ]

标题：图演化复杂性

标题： Complexity of graph evolutions

Authors:Jeffrey Gao, Paul C. Kainen

摘要：一个图的元素的排列是一个{\it 构造序列}，如果没有任何边在其任一端点之前列出。这种序列的复杂性通过查找放置边的延迟来研究，这是构造序列的{\it 机会成本}。为各种图提供了最大和最小成本的 c-序列，并用于衡量图构建程序的复杂性。

摘要： A permutation of the elements of a graph is a {\it construction sequence} if no edge is listed before either of its endpoints. The complexity of such a sequence is investigated by finding the delay in placing the edges, an {\it opportunity cost} for the construction sequence. Maximum and minimum cost c-sequences are provided for a variety of graphs and are used to measure the complexity of graph-building programs.

主题：	组合数学 (math.CO) ; 离散数学 (cs.DM)
MSC 类：	05A05, 05A17, 05C09, 05C78
ACM 类：	G.2.2; C.1.4
引用方式：	arXiv:2412.00212 [math.CO]
	(或者 arXiv:2412.00212v1 [math.CO] 对于此版本)
	https://doi.org/10.48550/arXiv.2412.00212

提交历史

来自： Paul Kainen [查看电子邮件]
[v1] 星期五， 2024 年 11 月 29 日 19:20:26 UTC (113 KB)

数学 > 组合数学

标题：图演化复杂性

标题： Complexity of graph evolutions

提交历史

获取论文：

参考文献与引用

收藏

文献和引用工具

与本文相关的代码，数据和媒体

演示

推荐器和搜索工具

arXivLabs：与社区合作伙伴的实验项目

数学 > 组合数学

标题： 图演化复杂性 显示英文标题

标题： Complexity of graph evolutions

提交历史

获取论文：

参考文献与引用

BibTeX 格式的引用

收藏

文献和引用工具

与本文相关的代码，数据和媒体

演示

推荐器和搜索工具

arXivLabs：与社区合作伙伴的实验项目

标题：图演化复杂性