Polynomial Time Algorithms For Two Classes Of Subgraph Problem

Sriraman Sridharan

首页> 外文期刊>RAIRO Operation Research >Polynomial Time Algorithms For Two Classes Of Subgraph Problem

【24h】

Polynomial Time Algorithms For Two Classes Of Subgraph Problem

机译：两类子图问题的多项式时间算法

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

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

摘要

We design a O(n~3) polynomial time algorithm for finding a (k - 1)- regular subgraph in a k-regular graph without any induced star K_(1.3)(claw-free). A polynomial time algorithm for rinding a cubic subgraph in a 4-regular locally connected graph is also given. A family of fc-regular graphs with an induced star K_(1.3) (k even,k ≥ 6), not containing any (k - 1)-regular subgraph is also constructed.

机译：我们设计了一种O（n〜3）多项式时间算法，用于在k正则图中找到（k-1）-正则子图，而没有任何诱发星K_（1.3）（无爪）。还给出了将三次子图浸入4规则局部连接图中的多项式时间算法。还构造了一个fc-正则图族，其诱导星K_（1.3）（k even，k≥6），不包含任何（k --1）-正则子图。

著录项

来源
《RAIRO Operation Research》 |2008年第3期|p.291-298|共8页
作者
Sriraman Sridharan;
展开▼
作者单位

Departement de Mathematiques et d'Inforniatique, Universite de Perpignan via Domitia, 52 Avenue Paul Alduy, 66100 Perpignan, France;

展开▼
收录信息美国《科学引文索引》(SCI);美国《工程索引》(EI);
原文格式 PDF
正文语种 eng
中图分类运筹学;
关键词
polynomial time algorithm; np-complete; graph; star; regular graph; perfect marching;

机译：多项式时间算法np完全图星形规则图完美行进;

相似文献

外文文献
中文文献
专利

1. Polynomial-time algorithms for SUBGRAPH ISOMORPHISM in small graph classes of perfect graphs [J] . Konagaya Matsuo, Otachi Yota, Uehara Ryuhei Discrete Applied Mathematics . 2016,第Null期

机译：完美图的小图类中子图等价的多项式时间算法
2. Polynomial and pseudo-polynomial time algorithms for different classes of the Distance Critical Node Problem [J] . Aringhieri Roberto, Grosso Andrea, Hosteins Pierre, Discrete Applied Mathematics . 2019,第期

机译：不同类别距离关键节点问题的多项式和伪多项式时间算法
3. A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics [J] . Leander Schietgat, Jan Ramon, Maurice Bruynooghe Annals of Mathematics and Artificial Intelligence . 2013,第4期

机译：平面图的多项式时间最大公共子图算法及其在化学信息学中的应用
4. Polynomial-Time Algorithms for Subgraph Isomorphism in Small Graph Classes of Perfect Graphs [C] . Matsuo Konagaya, Yota Otachi, Ryuhei Uehara Annual conference on theory and applications of models of computation . 2014

机译：完美图的小图类中子图同构的多项式时间算法
5. Polynomial time recognition and optimization algorithms on special classes of graphs. [D] . Johnson, Julie Lynn. 2003

机译：特殊图类上的多项式时间识别和优化算法。
6. Polynomial-Time Algorithms for Building a Consensus MUL-Tree [O] . Yun Cui, Jesper Jansson, Wing-Kin Sung -1

机译：建立共识MUL树的多项式时间算法
7. Polynomial time algorithms for two classes of subgraph problem [O] . Sridharan Sriraman 2008

机译：两类子图问题的多项式时间算法

Polynomial Time Algorithms For Two Classes Of Subgraph Problem

摘要

著录项

相似文献

相关主题

期刊订阅