权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Algorithmic Aspects of Intersection Graph Models

交叉图模型的算法方面

基本信息

批准号：
EP/K022660/1
负责人：
George Mertzios
金额：
$ 12.33万
依托单位：
Durham University
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2013
资助国家：
英国
起止时间：
2013 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FK022660%2F1
关键词：
Algorithmic Aspects Intersection Graph Models

项目摘要

The design and analysis of algorithms on graphs is a major sub-discipline of Computer Science. Graphs (composed of vertices and edges) are ubiquitous not only in Computer Science and Mathematics but across the whole spectrum of Science and Engineering. The vast range of applications of graphs result in a whole host of different properties of interest. This basic fact has motivated the extensive study of structured graph classes, i.e. of families of graphs that all share some common structural property. For example, when graphs are used to model networks-on-chips, it is necessary that such graphs are planar for they need to be laid out on the plane so that none of their edges cross. However, no matter which standard data structures we use to represent graphs, most important structural properties are complex enough to be "well hidden" within these basic representations. Fortunately, more sophisticated representations exist for many graphs that model practical applications. In particular, a graph is called an intersection graph of a family of sets, if we can bijectively assign a set of this family to a vertex of the graph, such that adjacencies between pairs of vertices in the graph correspond bijectively to non-empty intersections of the corresponding pairs of sets. Such a family of sets is then called the intersection model of the graph.It turns out that many important graph classes can be described as intersection graphs of set families that are derived from some kind of geometric configuration. Probably the most prominent example of this kind is that of interval graphs, i.e. the intersection graphs of intervals on the real line. The applications of intersection graphs of geometric objects straddle several practical fields, such as biology and bioinformatics (e.g. the physical mapping of DNA and the genome reconstruction), mobile computing and sensor networks, map labeling, etc. Specific intersection models provide a natural and intuitive understanding of the inherent structure of a class of graphs, and turn out to be extremely helpful in delivering efficient algorithms for hard optimization problems, as well as in proving hardness results. Consequently, it is of great importance to establish such intersection models that characterize certain families of graphs. Within the proposed research we plan to explore the various intersection models by which many important families of graphs can be represented, as well as to more deeply understand their underlying combinatorial structure. Moreover, we plan to devise new intersection models for important graph classes, for which no intersection model is known so far. Revealing the inherent properties of intersection models for graphs will essentially help us in understanding the boundaries of efficient computation, in both the traditional sense (polynomial vs. NP-hard) and in the sense of parameterized complexity.

图上算法的设计和分析是计算机科学的一个主要分支学科。图(由顶点和边组成)不仅在计算机科学和数学中普遍存在，而且在科学和工程的整个范围内都是普遍存在的。图的广泛应用导致了一大堆不同的感兴趣的性质。这一基本事实激发了对结构化图类的广泛研究，即具有共同结构性质的图族的研究。例如，当使用图来建模片上网络时，这种图必须是平面的，因为它们需要在平面上布局，以便它们的任何边都不会相交。然而，无论我们使用哪种标准数据结构来表示图形，大多数重要的结构属性都足够复杂，可以很好地隐藏在这些基本表示中。幸运的是，对于许多为实际应用程序建模的图，存在更复杂的表示。特别地，一个图称为集族的交图，如果我们可以双射地将这个集族的一个集合分配给这个图的一个顶点，使得图中的顶点对之间的邻接关系双射地对应于相应的集对的非空交。这样的集族被称为图的交集模型，许多重要的图类都可以描述为集族的交图，它们是由某种几何构形派生出来的。这类图最突出的例子可能是区间图，即实线上区间的交图。几何对象的交图的应用跨越了生物学和生物信息学(如DNA的物理映射和基因组重建)、移动计算和传感器网络、地图标注等几个实用领域。特定的交图模型提供了对一类图的内在结构的自然和直观的理解，并被证明在为困难的优化问题提供高效的算法以及证明困难结果方面非常有帮助。因此，建立这种刻画某些图族的交集模型是非常重要的。在拟议的研究中，我们计划探索各种交集模型，通过这些模型可以表示许多重要的图族，并更深入地了解它们潜在的组合结构。此外，我们计划为重要的图类设计新的交集模型，目前还没有已知的交集模型。揭示图的交集模型的内在性质将本质上帮助我们理解有效计算的边界，无论是在传统意义上(多项式vs.NP-Hard)还是在参数化复杂性意义上。

项目成果

期刊论文数量（10）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings

计算机科学数学基础 2013 - 第 38 届国际研讨会，MFCS 2013，奥地利克洛斯特新堡，2013 年 8 月 26-30 日。

DOI：
10.1007/978-3-642-40313-2_34
发表时间：
2013
期刊：
影响因子：
0
作者：
Felsner S
通讯作者：
Felsner S

Intersection graphs of L-shapes and segments in the plane

L 形和平面内线段的交图

DOI：
10.1016/j.dam.2016.01.028
发表时间：
2016
期刊：
Discrete Applied Mathematics
影响因子：
1.1
作者：
Felsner S
通讯作者：
Felsner S

Parameterized Domination in Circle Graphs

DOI：
10.1007/s00224-013-9478-8
发表时间：
2012-05
期刊：
Theory of Computing Systems
影响因子：
0.5
作者：
N. Bousquet;D. Gonçalves;G. B. Mertzios;C. Paul;Ignasi Sau;Stéphan Thomassé
通讯作者：
N. Bousquet;D. Gonçalves;G. B. Mertzios;C. Paul;Ignasi Sau;Stéphan Thomassé

The Complexity of Optimal Design of Temporally Connected Graphs.

时间连通图优化设计的复杂性。