• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Graph-theoretic concepts in computer science >A Graph Polynomial Arising from Community Structure (Extended Abstract)
【24h】

A Graph Polynomial Arising from Community Structure (Extended Abstract)

机译：来自社区结构的图多项式（扩展摘要）

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Inspired by the study of community structure in connection networks, we introduce the graph polynomial Q (G;x,y), as a bivariate generating function which counts the number of connected components in induced subgraphs. We analyze the features of the new polynomial. First, we re-define it as a subset expansion formula. Second, we give a recursive definition of Q (G; x, y) using vertex deletion, vertex contraction and deletion of a vertex together with its neighborhood, and prove a universality property. We relate Q (G; x, y) to the universal edge elimination polynomial introduced by I. Averbouch, B. Godlin and J.A. Makowsky (2008), which subsumes other known graph invariants and graph polynomials, among them the Tutte polynomial, the independence and matching polynomials, and the bivariate extension of the chromatic polynomial introduced by K. Dohmen, A. Ponitz, and P. Tittmann (2003). Finally we show that the computation of Q (G; x,y) is #P-hard, but Fixed Parameter Tractable for graphs of bounded tree-width and clique-width.
机译：受连接网络中社区结构研究的启发，我们引入了图多项式Q（G; x，y），作为双变量生成函数，该函数对诱导子图中的连接分量进行计数。我们分析新多项式的特征。首先，我们将其重新定义为子集扩展公式。其次，我们使用顶点删除，顶点收缩和顶点删除及其邻域来给出Q（G; x，y）的递归定义，并证明其通用性。我们将Q（G; x，y）与I.Averbouch，B.Godlin和J.A.引入的通用边缘消除多项式相关联。 Makowsky（2008）归纳了其他已知的图不变式和图多项式，其中包括Tutte多项式，独立和匹配多项式以及K. Dohmen，A。Ponitz和P. Tittmann（ 2003）。最后，我们证明Q（G; x，y）的计算是#P困难的，但是对于有界树宽和集团宽度的图，固定参数可牵引。

著录项

  • 来源
  • 会议地点 Montpellier(FR);Montpellier(FR)
  • 作者

    I. Averbouch; J.A. Makowsky; P. Tittmann;

  • 作者单位

    Department of Computer Science,Technion-Israel Institute of Technology, 32000 Haifa, Israel;

    Department of Computer Science,Technion-Israel Institute of Technology, 32000 Haifa, Israel;

    Fachbereich Mathematik-Physik-InformatikHochschule Mittweida, Mittweida, Germany;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 计算机网络;
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号