支配集問題與p重心問題在電腦科學與作業研究領域中，都是基礎而且重要的研究議題。本論文研究支配集問題與p重心問題的變形問題，像是外連通支配集問題、有權重的獨立支配集問題和連通p重心問題。

外連通支配集的定義為：在圖中所有頂點V 的子集合D 中，每一個頂點在V \ D中都至少與一個在D內的頂點相連接，而且圖中所有頂點去掉這個子集合D所包含的頂點後，剩下來的子圖必須要是連通的。給定一個圖G，在G上找出最小的外連通支配集D，我們稱為外連通支配集問題。

獨立支配集的定義為:一組點集合S，若在圖G中被稱為獨立支配集，則在點集合S中的任兩個頂點都不會相鄰，而且圖G上的任何頂點若不是與S中的頂點相鄰，就是與S點集合以外的頂點相鄰。若圖G上的每個頂點與每個邊都帶有權重值，定義為c(v)和c(e)，有權重的獨立支配集問題就是在圖G上找出一組權重加總為最小的獨立支配集D。

p重心問題的定義為:在網路上配置p個設施，使得需求點向離自己最近的設施尋求服務時，每個需求點尋求設施服務的距離，加總起來要是最小的。而我們研究的連通p重心問題，則是再加上這p個設施彼此之間要是互相連通的條件。

本論文第一個主題會在謝爾賓斯基相關圖形上找出最小的外連通支配集，並且證明推導出的精確值為外連通支配集問題的最佳解。第二個主題在串連並連圖形上，給出一個線性時間演算法，來找出權重最小的獨立支配集。最後我們證明連通p重心問題在邊上有兩種以上權重的完全圖上是NP-hard，並且在邊上有單一權重的區塊圖上給出一個線性時間演算法來找出連通p重心。

The dominating set problem and the $p$-median problem are both basic and important research topics in computer science and operations research. This dissertation studies the variant of the domination problem and the $p$-median problem, such as the outer-connected domination problem, the weighted independent domination problem and the connected $p$-median problem.

An outer-connected dominating set in a graph $G = (V,E)$ is a set of vertices $D\subseteq V$ satisfying the condition that, for each vertex $v\notin D$, vertex $v$ is adjacent to some vertex in $D$ and the subgraph induced by $V\backslash D$ is connected. The outer-connected dominating set problem is to find
an outer-connected dominating set with the minimum number of vertices.

A set $S$ of vertices in a graph $G=(V, E)$ is an independent dominating set of $G$ if no two vertices in $S$ are adjacent and every vertex not in $S$ is adjacent to a vertex in $S$.
Suppose every vertex $v\in V$ and every edge $e\in E$ are associated with a cost which is a real number, denoted by $c(v)$ and $c(e)$, respectively.
The weighted independent domination problem is to find an independent dominating set $D$ such that its total cost $c(D)=\sum_{x\in D}c(x)+\sum_{x\not\in D}\min\{c(x,y),\mbox{ for $y\in D$ and $(x,y)\in E$}\}$ is minimum.

The $p$-median problem is to locate $p$ facilities on a network so as to minimize the average distance from a demand point to its closest facility. We study a variant of the $p$-median problem in which the subgraph induced by all vertices in $p$-median must be connected, and this problem is called the connected $p$-median problem.

The first subject of this dissertation is to propose a way for finding a minimum outer-connected dominating set for each of those Sierpi$\acute{\mathrm{\bf n}}$ski-like Graphs. Furthermore, we also derive the exact values of outer-connected domination numbers of those graphs. The second subject is to find the minimum weighted independent dominating set in linear-time on series-parallel graphs. Finally, we show the connected $p$-median problem on complete graphs with two different edge weights is NP-complete and give a linear time algorithm on block graphs with unit edge weight.

[1] G. AgnarssonandR.Greenlaw, GraphTheoryModeling,Applications,and
Algorithms., PearsonEducation,Inc.(2007).
[2] M. H.Akhbari,R.Hasni,O.Favaron,H.Karami,andS.M.Sheikholeslami,
On theouter-connecteddominationingraphs, Journal ofCombinatorialOpti-
mization 26 (2013)10-18.
[3] R. BenkocziandB.Bhattacharya,Anewtemplateforsolving p-median prob-
lems fortreesinsub-quadratictime, LNCS 3669 (2005)271-282.
[4] T. Beyer,S.Hedetniemi,S.Mitchell,andA.Proskurowski,Independentdom-
ination intrees, Proceedingsofthe8thSoutheasternConferenceonCombina-
torics, GraphTheory,andComputing,UtilitiesMathematica,Winnipeg(1997)
321-328.
[5] M. Blum,R.W.Floyd,V.R.Pratt,R.L.RivestandR.E.Tarjan,Time
boundsforselection, J. Comput.Syst.Sci. 7 (1972)448-461.
[6] A. Brandstadt,V.D.Chepoi,andF.F.Dragan,Thealgorithmicuseofhypertree
structure andmaximumneighbourhoodorderings, DiscreteAppliedMathemat-
ics 82 (1998)43-77.
[7] R.E. BurkardandJ.Krarup,Alinearalgorithmforthepos/neg-weighted1-
median problemonacactus, Computing 60 (1998)193-215.
[8] R. E.BurkardandJ.Fathali,Apolynomialmethodforthepos/negweighted
3-median problemonatree, Math. MethodOper.Res. 65 (2007)229-238.
[9] R.E. BurkardandJ.Hatzl,Medianproblemswithpositiveandnegativeweights
on cyclesandcacti, J. Comb.Optim. 20 (2008)27-46.
[10] M.S. Chang,E cientalgorithmsfortheweighteddominationproblemoninter-
valandcircular-arcgraphs, SIAM JournalonComputing 27 (1998)1671-1694.
[11] G. J.Chang,TheweightedindependentdominationproblemisNP-complete
for chordalgraphs, DiscreteAppliedMathematics 143 (2004)351-352.
[12] S. C.Chang,C.K.Yen,Y.L.WangandJ.J.Liu,TheNP-completenessofthe
Connected p-MedianProblemonBipartiteGraphsandSplitGraphs, CHIANG
MAI JSCI 40 (2013)83-88.
[13] G.H. ChenandD.R.Duh,Topologicalproperties,communication,andcompu-
tation onWK-recursivenetworks, Networks 24 (1994)303-317.
[14] G. T.Chen,W.DingandS.W.Li,Connected p-median problemsintree
networks, Journal ofHangzhouDianziUniversity 29 (2009)89-91.
[15] G. T.Chen,S.XinandS.H.Cui,Theconnected p-median problemonthe
3-cactus graph, Journal ofHangzhouDianziUniversity 30 (2010)77-80.
[16] Y. K.Cheng,L.Y.KangandC.H.Lu,Thepos/neg-weighted1-medianprob-
lem ontreegraphswithsubtree-shapedcustomers, Theor.Comput.Sci. 411
(2010) 1038-1044.
[17] D.G. CorneilandY.Perl,Clusteringanddominationinperfectgraphs, Discrete
AppliedMathematics 9 (1984)27-40.
[18] J. Cyman,Theouter-connecteddominationnumberofagraph, Australasian
Journal ofCombinatorics 38 (2007)35-46.
[19] M. S.Daskin, Networks andDiscreteLocation,Models,Algorithms,andAppli-
cations. New York:JohnWiley&Sons,Inc.,1995.
[20] Z. DreznerandH.Hamacher, Facilitylocation:applicationsandtheory, New
York:BerlinHeidelberg,2002.
[21] D.R. DuhandG.H.Chen,TopologicalpropertiesofWK-recursivenetworks,
Journal ofParallelandDistributedComputing 23 (1994)468-474.
[22] M. Farber,Independentdominationinchordalgraphs, OperationsResearch
Letters 1 (1982)134-138.
[23] M. FarberandJ.M.Keil,Dominationinpermutationgraphs, Journal ofAlgo-
rithms 6 (1985)309-321.
[24] M. R.GareyandD.S.Johnson, Computers andIntractability:AGuidetothe
TheoryofNP-Completeness, New York:W.H.Freeman&Co.,1978.
[25] M.R. Garey,D.S.Johnson,ComputersandIntractability:AGuidetotheThe-
ory ofNP-Completeness, W.H.Freeman,SanFrancisco (1979).
[26] B. GavsihandS.Sridhar,Computingthe2-medianontreenetworksin
O(n log n) time, Networks 26 (1995)305-317.
[27] A. J.Goldman,Optimalcenterlocationinsimplenetworks, Transport.Sci. 5
(1971) 212-221.
[28] J. Hatzl,Medianproblemonwheelsandcactusgraphs, Computing 80 (2007)
377-393.
[29] A.M. HinzandA.Schief,TheaveragedistanceontheSierpi nskigasket, Prob-
ability TheoryRelatedFields 87 (1990)129-138.
[30] A.M. Hinz,Pascal'striangleandtheTowerofHanoi, AmericanMathematical
Monthly 99 (1992)538-544.
[31] A.M. Hinz,S.Klav zar,U.Milutinovi c,D.Parisse,andC.Petr,Metricprop-
erties oftheTowerofHanoigraphsandStern'sdiatomicsequence, European
Journal ofCombinatorial 26 (2005)693-708.
[32] A.M. HinzandDanieleParisse,TheAverageEccentricityofSierpi nskiGraphs,
GraphsandCombinatorics 28 (2012)671-686.
[33] W. Irving,Onapproximatingtheminimumindependentdominatingset, Information ProcessingLetters 37 (1991)197-200.
[34] M. JakovacandS.Klav zar,Vertex-,edge-andtotal-coloringsofSierpi nski-like
graphs, DiscreteMathematics 309 (2009)1548-1556.
[35] H. JiangandE.Shan,Outer-connecteddominationnumberingraphs, Utilitas
Mathematica 81 (2010)265-274.
[36] V.A. Kaimanovich,RandomwalksonSierpi nskigraphs:hyperbolicityand
stochastichomogenization,in:FractalsinGraz2001, Editors:P.Grabnerand
W. Woess,Birkhauser,2003,pp.145-183.
[37] O. Karivand,S.L.Hakimi,Analgorithmicapproachtonetworklocationprob-
lems, PartII:p-medians, Siam. J.Appl.Math. 27 (1979)539-560.
[38] T. Kikuno,N.Yoshida,andY.Kakuda,Alineartimealgorithmforthedomina-
tion numberofaseries-parallelgraph, DiscreteAppliedMathematics 5 (1983)
299-311.
[39] S. Klav zarandU.Milutinovi c,Graphs S(n; k) andavariantoftheTowerof
Hanoi problem, CzechoslovakMathematicalJournal 47 (1997)95-104.
[40] S. Klav zar,U.Milutinovi c,andC.Petr,1-perfectcodesinSierpi nskigraphs,
BulletinoftheAustralianMathematicalSociety 66 (2002)369-384.
[41] S. Klav zarandB.Mohar,CrossingnumbersofSierpi nski-likegraphs, Journal
of GraphTheory 50 (2005)186-198.
[42] S. Klav zar,ColoringSierpi nskigraphsandSierpi nskigasketgraphs, Taiwanese
Journal ofMathematics 12 (2008)513-522.
[43] F. KlixandK.Rautenstrauch-Goede,Struktur-undKomponentenanalysevon
Problemlosungsprozessen, Zeitschrift furPsychologie 174 (1967)167-193.
[44] Y. F.LanandY.L.Wang,Anoptimalalgorithmforsolvingthe1-median
problem onweighted4-cactusgraphs, Eur. J.Oper.Res. 122 (2000)602-610.
[45] C.H.Lin,J.J.Liu,Y.L.Wang,andW.C.K.Yen,ThehubnumberofSierpi nski-
likegraphs, TheoryofComputingSystems 49(3) (2011)588-600.
[46] C.H.Lin,J.J.Liu,andY.L.Wang,Globalstrongdefensivealliancesof
Sierpi nski-likegraphs, TheoryofComputingSystems 53(3) (2013)365-385.
[47] J. MarkKeil,andD.Pradhan,Computingaminimumouter-connecteddomi-
nating setfortheclassofchordalgraphs, Information ProcessingLetters 113
(2013) 552-561.
[48] E. F.Moore,TheShortestPathThroughaMaze, ProceedingsofInternational
Symposium:SwitchingTheory,HarvardUniversity.Press,Cambridge, (1959)
285-292.
[49] H. MullerandA.Brandstadt,TheNP-completenessofSteinerTreeandDom-
inating SetforChordalBipartiteGraphs, TheoreticalComputerScience 53
(1987) 257-265.
[50] D. Parisse,OnsomemetricpropertiesoftheSierpi nskigraphs S(n; k), Ars
Combinatoria 90 (2009)145-160.
[51] J. Pfa ,R.LaskarandS.Hedetniemi,Linearalgorithmsforindependentdomi-
nation andtotaldominationinseries-parallelgraphs, CongressusNumerantium
45 (1984)71-82.
[52] J. Reese,Solutionmethodsforthe p-median problem:anannotatedbibliogra-
phy, Networks 48 (2006)125-142.
[53] D. Romik,ShortestpathsintheTowerofHanoigraphand niteautomata,
SIAM JournalonDiscreteMathemathics 20 (2006)610-622.
[54] H. Sydow,ZurmetrischenErfasungvonsubjektivenProblemzustandenund
zu derenVeranderungimDenkprozes, Zeitschrift fur Psychologie 177 (1970)
145-198.
[55] A. Tamir,An O(pn2) algorithmforthe p-median andrelatedproblemsontree
graphs, Oper.Res.Lett. 19 (1996)59-64.
[56] A.M. TeguiaandA.P.Godbole,Sierpi nskigasketgraphsandsomeoftheir
properties, AustralasianJournalofCombinatorics 35 (2006)181-192.
[57] A. Toru,Alineartimealgorithmfor ndingtheminimumpaired-dominating
set inseries-parallelgraphs, IPSJ SIGNotes 40 (2007)15-22.
[58] G.D.VecchiaandC.Sanges,ArecursivelyscalablenetworkVLSIimplementa-
tion, FutureGenerationsComputerSystems 4 (1988)235-243.
[59] C. E.Vieira,HeuristicsfortheConnectedp-MedianProblem, Ph.D. Thesis,
Pontif ciaUniversidadeCat olicadoRiodeJaneiro,2006.
[60] D.B. West, IntroductiontoGraphTheory.(2nd ed.),River,N.J.:Prentice-Hall, 2001.
[61] B. H.Yang,Z.G.Fang,J.S.ZhaoandS.Y.Ye,Thelocationproblem
in emergencymanagementconsideringuncertaininformation, Proceedingsof
2009 IEEEInternationalConferenceonGreySystemsandIntelligentServices,
(2009) 10-12.
[62] C.C.YenandR.C.T.Lee,Alineartimealgorithmtosolvetheweightedperfect
domination probleminseries-parallelgraphs, EuropenJournalofOperational
Research 73 (1994)192-198.
[63] X. Q.Zhang,L.Y.KangandY.K.Cheng,Thepos/neg-weightedmedianprob-
lem onblockgraphswithsubgraph-shapedcustomers, Computing 88 (2010)
97-110.