A representation for the modules of a graph and applications

被引：0
作者：
Klein, Sulamita [1 ]
Szwarcfiter, Jaime L. [2 ]
机构：
[1] Institute de Matemática And, COPPE/Sistemas, UFRJ, 21945-970 - Rio de Janeiro, RJ
[2] Institute de Matemática, NCE and COPPE/Sistemas, UFRJ, 20001-970 - Rio de Janeiro, RJ
来源：
Journal of the Brazilian Computer Society | 2003年 / 9卷 / 01期
关键词：
Algorithms; Bipartite tournaments; Graphs; Ideals; Modules; Posets;
D O I：
10.1590/S0104-65002003000200002
中图分类号：
学科分类号：
摘要：
We describe a simple representation for the modules of a graph G. We show that the modules of G are in one-to-one correspondence with the ideals of certain posets. These posets are characterized and shown to be layered posets, that is, transitive closures of bipartite tournaments. Additionaly, we describe applications of the representation. Employing the above correspondence, we present methods for solving the following problems: (i) generate all modules of G, (ii) count the number of modules of G, (iii) find a maximal module satisfying some hereditary property of G and (iv) find a connected non-trivial module of G.
引用
收藏
页码：9 / 16
页数：7
相关论文
共 14 条
  • [1] Buer B., Mohring R.H., A fast algorithm for the decomposition of graphs and posets, Math. Oper. Res., 8, pp. 170-184, (1983)
  • [2] Cournier A., Habib M., A new linear algorithm for modular decomposition, CAAP'94: 19th International Colloquium, Lectures Notes in Computer Science, pp. 68-82, (1994)
  • [3] Dahlhaus E., Gustedt J., McConnel R.M., Efficient and pratical modular decomposition, Proceedings of the Eight Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 26-35, (1997)
  • [4] Ehrenfeucht A., Gabow H.N., McConnel R.M., Sullivan S.J., An O(n<sup>2</sup>) divide-and-conquer algorithms for the prime tree decomposition of two-structures and modules decompositions of graphs, J. of Algorithms, 16, pp. 283-294, (1994)
  • [5] Gallai T., Transitiv orientierbare graphen, Acta Math. Acad. Sci. Hungar., 18, pp. 25-66, (1967)
  • [6] Golumbic M.C., Algorithmic graph theory and perfect graphs, Academic Press, (1980)
  • [7] Habib M., Maurer M.C., On the X-join decomposition for undirected graphs, Discrete Appl. Math., 1, pp. 201-207, (1979)
  • [8] Kelly D., Comparability graphs, Graphs and Orders, pp. 3-40, (1985)
  • [9] McConnel R.M., Spinrad J., Linear-time modular decomposition and efficient transitive orientation of comparability graphs, Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 536-545, (1994)
  • [10] McConnel R.M., Spinrad J., Linear -time transitive orientation, Proceedings of the Eight Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 19-25, (1997)
12