nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.07.2016

Complexity of domination, hamiltonicity and treewidth for tree convex bipartite graphs

verfasst von: Hao Chen, Zihan Lei, Tian Liu, Ziyang Tang, Chaoyi Wang, Ke Xu

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Tree convex bipartite graphs generalize convex bipartite graphs by associating a tree, instead of a path, with one set of the vertices, such that for every vertex in another set, the neighborhood of this vertex induces a subtree. There are seven graph problems, grouped into three classes of domination, Hamiltonicity and treewidth, which are known to be \(\mathcal {NP}\)-complete for bipartite graphs, but tractable for convex bipartite graphs. We show \(\mathcal {NP}\)-completeness of these problems for tree convex bipartite graphs, even when the associated trees are stars or combs respectively.

Vorheriger Artikel Constrained pairwise and center-star sequences alignment problems

Nächster Artikel Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Arnborg S, Corneil DG, Proskurowski A (1987) Complexity of finding embeddings in a k-tree. SIAM J Algebr Discret Methods 8:277–284MathSciNetCrossRefMATH

Brandstäd A, Le VB, Spinrad JP (1999) Graph classes—a survey. Society for Industrial and Applied Mathematics, PhiladelphiaCrossRef

Chen L, Lu C, Zeng Z (2010) Labelling algorithms for paired-domination problems in block and interval graphs. J Comb Optim 19:457–470MathSciNetCrossRefMATH

Damaschke P, Muller H, Kratsch D (1990) Domination in convex and chordal bipartite graphs. Inform Proc Lett 36:231–236MathSciNetCrossRefMATH

Garey MR, Johnson DS (1979) Computers and intractability, a guide to the theory of NP-completeness. W.H. Freeman and Company, New YorkMATH

Golumbic MC, Goss CF (1978) Perfect elimination and chordal bipartite graphs. J Graph Theory 2:155–163MathSciNetCrossRefMATH

Golumbic MC (2004) Algorithmic graph theory and perfect graphs, Annals of discrete mathematics, vol 57, 2nd edn. Elsevier B.V., Amsterdam

Grover F (1967) Maximum matching in a convex bipartite graph. Nav Res Logist Q 14:313–316CrossRef

Hung R-W (2012) Linear-time algorithm for the paired-domination problem in convex bipartite graphs. Theory Comput Syst 50:721–738MathSciNetCrossRefMATH

Irving W (1991) On approximating the minimum independent dominating set. Inform Process Lett 37:197–200MathSciNetCrossRefMATH

Jiang W, Liu T, Ren T, Xu K (2011) Two hardness results on feedback vertex sets. Proceedings of FAW-AAIM 2011, pp 233–243

Jiang W, Liu T, Wang C, Xu K (2013) Feedback vertex sets on restricted bipartite graphs. Theory Comput Sci 507:41–51MathSciNetCrossRefMATH

Jiang W, Liu T, Xu K (2011) Tractable feedback vertex sets in restricted bipartite graphs. Proceedings of COCOA 2011, pp 424–434

Karp R (1972) Complexity of computer computations., Reducibility among combinatorial problemsPlenum Press, New York

Kloks T (1994) Treewidth: computations and approximations. Springer, BerlinCrossRefMATH

Kloks T, Kratsch D (1995) Treewidth of chordal bipartite graphs. J Algorithms 19:266–281MathSciNetCrossRefMATH

Kloks T, Liu CH, Pon SH (2011) Feedback vertex set on chordal bipartite graphs. arXiv:1104.3915

Kloks T,Wang YL (2013) Advances in graph slgorithms. Manuscript

Krishnamoorthy MS (1975) An NP-hard problem in bipartite graphs. SIGACT News 7(1):26MathSciNetCrossRef

Liang YD, Blum N (1995) Circular convex bipartite graphs: maximum matching and Hamiltonian circuits. Inf Process Lett 56:215–219MathSciNetCrossRefMATH

Liang YD, Chang MS (1997) Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs. Acta Informatica 34:337–346MathSciNetCrossRef

Liu T (2014) Restricted bipartite graphs: comparison and hardness results. Proceddings of AAIM, pp 241–252

Liu T, Lu Z, Xu K (2015) Tractable connected domination for restricted bipartite graphs. J Comb Optim 29:247–256MathSciNetCrossRefMATH

Lu M, Liu T, Xu K (2013) Independent domination: reductions from circular- and triad-convex bipartite graphs to convex bipartite graphs. Proceedings of FAW-AAIM, pp 142–152

Lu M, Liu T, Tong W, Lin G, Xu K (2014) Set cover, set packing and hitting set for tree convex and tree-like set systems. Proceedings of TAMC, pp 248–258

Liu T, Xu K (2015) Union-closed tree convex sets. Proceedings of FAW, to appear

Müller H (1996) Hamiltonian circuits in chordal bipartite graphs. Disc Math 156(1–3):291–298MathSciNetCrossRefMATH

Müller H, Brandstät A (1987) The NP-completeness of steiner tree and dominating set for chordal bipartite graphs. Theory Comput Sci 53(2–3):257–265MathSciNetCrossRefMATH

Panda BS, Prahan D (2013) Minimum paired-dominating set in chordal graphs and perfect elimination bipartite graphs. J Comb Optim 26:770–785MathSciNetCrossRefMATH

Pandey A, Panda BS (2015) Domination in some subclasses of bipartite graphs. Proceedings of CALDAM 2015, pp 169–180

Pfaff J, Laskar R, Hedetniemi ST (1983) NP-completeness of total and connected domination, and irredundance for bipartite graphs. Technical Report 428, Department Mathematical Sciences, Clemenson University

Song Y, Liu T, Xu K (2012) Independent domination on tree convex bipartite graphs. Proceedings of FAW-AAIM 2012, pp 129–138

Wang C, Liu T, Jiang W, Xu K (2012) Feedback vertex sets on tree convex bipartite graphs. Proceedings of COCOA 2012, pp 95–102

Yannakakis M (1981) Node-deletion problem on bipartite graphs. SIAM J Comput 10:310–327MathSciNetCrossRefMATH

Titel: Complexity of domination, hamiltonicity and treewidth for tree convex bipartite graphs
verfasst von: Hao Chen
Zihan Lei
Tian Liu
Ziyang Tang
Chaoyi Wang
Ke Xu
Publikationsdatum: 01.07.2016
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 1/2016
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-015-9917-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2016

A complexity dichotomy and a new boundary class for the dominating set problem

Strong minimum energy hierarchical topology in wireless sensor networks

New analysis and computational study for the planar connected dominating set problem

Distributed wireless link scheduling in the SINR model

Constrained pairwise and center-star sequences alignment problems

Partial degree bounded edge packing problem for graphs and -uniform hypergraphs