PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

A Generalization of Join and an Algorithmic Recognition Problem

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
We consider a new graph operation c2-join which generalizes join and co-join. We show that odd hole-free graphs (odd antihole-free graphs) are closed under c2-join and describe a polynomial time algorithm to recognize graphs that admit a c2-join. The time complexity of the (a) recognition problem, (b) maximum weight independent set (MWIS) problem, and (c) minimum coloring (MC) problem for odd hole-free graphs are still unknown. Let H be an odd hole-free graph that contains an odd antihole as an induced subgraph and GH be the class of all graphs generated from the induced subgraphs of H by using c2-join recursively. Then GH is odd hole-free, contains all P4-free graphs, complement of all bipartite graphs, and some imperfect graphs. We show that the MWIS problem, maximum weight clique (MWC) problem, MC problem, and minimum clique cover (MCC) problem can be solved efficiently for GH.
Wydawca
Rocznik
Strony
81--91
Opis fizyczny
Bibliogr. 30 poz., rys.
Twórcy
autor
  • Indian Institute of Information Technology Design & Manufacturing (IIITD&M) Kancheepuram, Chennai, India
autor
  • Indian Institute of Information Technology Design & Manufacturing (IIITD&M) Kancheepuram, Chennai, India
Bibliografia
  • [1] Corneil DG, Lerchs H, Burlingham LS. Complement reducible graphs. Discrete Applied Mathematics. 1981;3:163–174.
  • [2] Chudnovsky M, Seymour P. The Structure of Claw-free Graphs. In: Proceedings of the British Combinatorial Conference. vol. 327. Cambridge University Press; 2005. p. 153–171.
  • [3] Atay FM, Biyikoğlu T. Graph operations and synchronization of complex networks. Physical Review. 2005;72(016217). Available from: http://dx.doi.org/10.1103/PhysRevE.72.016217. doi:10.1103/PhysRevE.72.016217.
  • [4] Brualdi RA. The Mutually Beneficial Relationship of Graphs and Matrices. In: CBMS Regional Conference Series in Mathematics, 12-16 July, 2010. vol. 115; 2011. ISBN:10:0-8218-5315-5. Available from: http://www.ams.org/publications/authors/books/postpub/cbms-115/\#sthash.yN340hUg.dpuf.
  • [5] Chudnovsky M, Penev I, Scott A, Trotignon N. Substitution and _-boundedness. Journal of Combinatorial Theory. 2013;103(5):567–586.
  • [6] Cvetković DM, Rowlinson P, Simić S. An Introduction to the Theory of Graph Spectra. vol. 75. Cambridge University Press, Cambridge-New York; 2010. Available from: http://dx.doi.org/10.1017/CBO9780511801518.
  • [7] Kamsu-Foguem B, Chapurlat V. Requirements modelling and formal analysis using graph operations. International Journal of Production Research. 2007;44(17):3451–3470. doi:10.1080/00207540500499377.
  • [8] Conforti M, Cornuéjols G, Liu X, Vušković K, Zambelli G. Odd hole recognition in graphs of bounded clique size. SIAM Journal of Discrete Mathematics. 2006;20(1):42–48. doi:10.1137/S089548010444540X.
  • [9] Conforti M, Cornuéjols G, Vušković K. Decomposition of odd hole-free graphs by double star cutsets and 2-joins. Discrete Applied Mathematics. 2004;141(1-3):41–91. doi:10.1016/S0166-218X(03)00364-0.
  • [10] Vušković K. Even hole-free graphs: A Survey. Applicable Analysis and Discrete Mathematics. 2010;4:219–240.
  • [11] West DB. Introduction to Graph Theory. Prentice Hall, USA; 1996.
  • [12] Bodlaender HL, Brandstädt A, Kratsch D, Rao M, Spinrad JP. On algorithms for fP5; gemg-free graphs. Theoretical Computer Science. 2005;349(1):2–21. doi:10.1016/j.tcs.2005.09.026.
  • [13] Brandstädt A, Mahfud S. Maximum weight stable set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time. Information Processing Letters. 2001;84(5):251–259. doi:10.1016/S0020-0190(02)00291-0.
  • [14] Gallai T. Transitiv orientierbare Graphen. Acta Mathematica Academia Scientia Hungarica. 1967;18:25–66.
  • [15] Giakoumakis V, Rusu I. Weighted parameters in fP5; P5g-free graphs. Discrete Applied Mathematics. 1997; 80:255–261.
  • [16] Habib M, Maurer MC. On the X-join decomposition of undirected graphs. Discrete Applied Mathematics. 1979;1:201–207.
  • [17] Hoáng CT, Reed B. Some classes of perfectly orderable graphs. Journal of Graph Theory. 1989;13(4):445–463. doi:10.1002/jgt.3190130407.
  • [18] Möhring RH. Algorithmic aspect of the substitution decomposition in optimization over relations, set systems and boolean functions. Annals of Operations Research. 1985;4:195–225.
  • [19] McConnell RM, Spinrad JP. Modular decomposition and transitive orientation. Discrete Mathematics. 1999; 201:189–241.
  • [20] Brandstädt A, Le VB, Spinrad JP. Graph Classes - A Survey. SIAM, Society for Industrial and Applied Mathematics, Philadelphia; 1999. ISBN:978-0-898714-32-6.
  • [21] Martin B, Paulusma D. The computational complexity of disconnected cut and 2K2 partition. In: 17th Int. Conf. on Principles and Practice of Constraint Programming. vol. 6876. LNCS; 2011. p. 561–575. doi:10.1007/978-3-642-30642-6.
  • [22] Lozin VV, Milanic M. A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. In: Proceeding SODA ’06 Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. vol. 6. SIAM Journal of Discrete Algorithms; 2008. p. 595–604. ISBN:0-89871-605-5.
  • [23] Desler JF, Hakimi SL. On finding a maximum stable set of a graph. In: Proc. 4-th Annual Princeton Conference on Information Science and System. Princeton, NJ; 1970. p. 459–462.
  • [24] Broersma HJ, Capponi A, Paulusma D. A new algorithm for on-line coloring bipartite graphs. SIAM Journal of Discrete Mathematics. 2008;22(1):72–91. Available from: http://dx.doi.org/10.1137/060668675. doi:10.1137/060668675.
  • [25] Kierstead HA, Penrice SG, Trotter WT. On-line and rst-t coloring of graphs which do not induce P5. SIAM Journal of Discrete Mathematics. 1995;8(4):485–498. doi:10.1137/S0895480191218861.
  • [26] Kierstead HA, Trotter WT. Colorful induced subgraphs. Discrete Mathematics. 1992;101(1-3):165–169.
  • [27] Kisielewicz A, Szykula M. Rainbow induced subgraphs in proper vertex colorings. Fundamenta Informaticae. 2011;111(4):437–451. ISBN:0169-2968.
  • [28] Simson D. Algorithms determining matrix morsifications, Weyl orbits, Coxeter polynomials and mesh geometries of roots for Dynkin diagrams. Fundamenta Informaticae. 2013;123:447–490. doi:10.3233/FI-2013-820.
  • [29] Simson D. A framework for Coxeter spectral analysis of edge-bipartite graphs, their rational morsifications and mesh geometries of root orbits. Fundamenta Informaticae. 2013;124:309–338. doi:10.3233/FI-2013-836.
  • [30] Simson D. A Coxeter-Gram classification of simply laced edge-bipartite graphs. SIAM Journal of Discrete Mathematics. 2013;27(2):827–854. doi:10.1137/110843721.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-b9143e61-4aba-4b7b-9b6a-364937a88f01
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.