Matchings of Intersection Graphs and the Maximum Genus Problem.

机译：相交图与最大类问题的匹配。

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

The maximum genus of a connected graph is defined to be the maximum integer g for which the graph has a cellular embedding in an orientable surface of genus g. We present the two most popular methods used to determine the maximum genus of a connected graph, contributed by Xuong and Nebesky, survey the polynomial-time algorithms available for finding a maximum genus embedding, and discuss the shortcomings of those algorithms.;We develop new results on the relationship between maximum genus and maximum matchings on intersection graphs, of spanning trees and cotrees, and introduce a new class of intersection graphs, called facial intersection graphs, defined for a given plane embedding. We show that for particular planar 2-connected graphs and for embeddings with certain properties, we can calculate the maximum genus using a standard matching algorithm on an optimal facial intersection graph.

机译：连接图的最大属定义为图在g属的可定向曲面中具有细胞嵌入的最大整数g。我们介绍了Xuong和Nebesky提出的用于确定连接图的最大类的两种最受欢迎的方法，调查了可用于找到最大类嵌入的多项式时间算法，并讨论了这些算法的缺点。得出跨树和共树的相交图上最大属和最大匹配之间的关系的结果，并介绍了为给定平面嵌入定义的一类新的相交图，称为面部相交图。我们表明，对于特定的平面2连通图和具有某些属性的嵌入，我们可以在最佳人脸相交图上使用标准匹配算法来计算最大属。

著录项

作者
El Sherif, Lara.;
展开▼
作者单位

The George Washington University.;

展开▼
授予单位 The George Washington University.;
学科 Mathematics.
学位 Ph.D.
年度 2016
页码 127 p.
总页数 127
原文格式 PDF
正文语种 eng
中图分类
关键词

相似文献

外文文献
中文文献
专利

1. Finding Maximum Induced Matchings in Subclasses of Claw-Free and P_5-Free Graphs, and in Graphs with Matching and Induced Matching of Equal Maximum Size [J] . Daniel Kobler, Udi Rotics Algorithmica . 2003,第4期

机译：在无爪图和无P_5图的子类中以及在具有相等且最大大小相等的匹配和归纳匹配的图中查找最大诱导匹配
2. The graphs with maximum induced matching and maximum matching the same size [J] . Kathie Cameron, Tracy Walker Discrete mathematics . 2005,第1a3期

机译：具有最大诱导匹配和最大匹配相同大小的图
3. The maximum genus, matchings and the cycle space of a graph [J] . Fu Hung-Lin, ?koviera Martin, Tsai Ming-Chun Czechoslovak Mathematical Journal . 1998,第2期

机译：图的最大属，匹配和循环空间
4. Maximum Cliques in Graphs with Small Intersection Number and Random Intersection Graphs [C] . Sotiris Nikoletseas, Christoforos Raptopoulos, Paul G. Spirakis International Symposium on Mathematical Foundations of Computer Science . 2012

机译：具有小交叉点数和随机交叉图的图中的最大族位
5. The genus of partitions and c-trees: Boolean decompositions and the graphs, Pruefer codes and perfect matchings of genus 0 c-trees . [D] . Hough, David Southerton. 2001

机译：分区和c树的属：布尔分解和图，pruefer码以及0类c树的完全匹配。
6. Clustering analysis of microRNA and mRNA expression data from TCGA using maximum edge-weighted matching algorithms [O] . Lizhong Ding, Zheyun Feng, Yongsheng Bai 2019

机译：使用最大边缘加权匹配算法对TCGA中microRNA和mRNA表达数据进行聚类分析
7. Finding Maximum Induced Matchings in Subclasses of Claw-Free and P5-Free Graphs, and in Graphs with Matching and Induced Matching of Equal Maximum Size [O] . Daniel Kobler, Udi Rotics 2003

机译：在无爪和无p5图的子类中以及具有相等最大尺寸的匹配和诱导匹配的图中查找最大诱导匹配

Matchings of Intersection Graphs and the Maximum Genus Problem.

摘要

著录项

相似文献

相关主题

期刊订阅