nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.01.2015

Tractable connected domination for restricted bipartite graphs

verfasst von: Tian Liu, Zhao Lu, Ke Xu

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

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Connected domination, i.e. the problem of finding a minimum connected dominating set in a graph, was known to be \(\mathcal {NP}\)-complete for chordal bipartite graphs, but to be tractable for convex bipartite graphs. In this paper, connected domination is shown to be tractable for circular- and triad-convex bipartite graphs respectively, by efficient reductions from these graphs to convex bipartite graphs.

Vorheriger Artikel Improved local search for universal facility location

Nächster Artikel An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs

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

Akhbari MH, Hasni R, Favaron O, Karami H, Sheikholeslami SM (2013) On the outer-connected domination in graphs. J Comb Optim 26:10–18CrossRefMATHMathSciNet

Damaschke P, Müller H, Kratsch D (1990) Domination in convex and chordal bipartite graphs. Inf Process Lett 36(5):231–236CrossRefMATH

Du H, Wu W, Shan S, Kim D, Lee W (2012) Constructing weakly connected dominating set for secure clustering in distributed sensor network. J Comb Optim 23:301–307CrossRefMATHMathSciNet

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

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

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

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

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

Li Y, Wu Y, Ai C, Beyah R (2012) On the construction of \(k\)-connected \(m\)-dominating sets in wireless networks. J Comb Optim 23:118–139CrossRefMATHMathSciNet

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

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

Lu Z, Liu T, Xu K (2013b) Tractable connected domination for restricted bipartite graphs (Extended Abstract). In: Proceedings of COCOON, pp 721–728

Lu Z, Lu M, Liu T, Xu K (2013c) Circular convex bipartite graphs: feedback vertex set. In: Proceedings of COCOA, pp 272–283

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

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

Sampathkumar E, Walikar HB (1979) The connected domination number of a graph. Math Phys Sci 13(6):607–613MATHMathSciNet

Shang W, Yao F, Wan P, Hu X (2008) On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs. J Comb Optim 16:99–106CrossRefMATHMathSciNet

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

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

Titel: Tractable connected domination for restricted bipartite graphs
verfasst von: Tian Liu
Zhao Lu
Ke Xu
Publikationsdatum: 01.01.2015
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 1/2015
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-014-9729-x

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/2015

Covering tree with stars

Randomized parameterized algorithms for -Packing and Co-Path Packing problems

Online unbounded batch scheduling on parallel machines with delivery times

Improved lower bounds for the online bin packing problem with cardinality constraints

A structural transformation from p- to MSVL

Improved approximation algorithms for computing disjoint paths subject to two constraints