文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Skodinis NP-Completeness of some tree-clustering problems. Graph Drawing `98, LNCS 1547
侵权投诉

Skodinis NP-Completeness of some tree-clustering problems. Graph Drawing `98, LNCS 1547

Abstract A graph is a tree of paths (cycles), if its vertex set can be partitioned into clusters, such that each cluster induces a simple path (cycle), and the clusters form a tree. Our main result states that the problem whether or not a given graph is a

NP-CompletenessofSomeTree-ClusteringProblems

Skodinis NP-Completeness of some tree-clustering problems. Graph Drawing `98, LNCS 1547

Skodinis NP-Completeness of some tree-clustering problems. Graph Drawing `98, LNCS 1547

289

(b)(c)

Figure1.Drawingsofatreeofpaths

ofcyclesandsoon.Itiseasytoseethateveryn×m-gridisapathofpathsandevery2n×2n-gridisapathofcycles.Tothecontraryeverycliquewithmorethanfourverticesisneitherapathofpathsnoratreeofpaths.

Two-levelclusteredgraphshavebeende nedinasyntacticwaybyKratochv´ let.al.[12].Theycanbedrawnaccordingtotheirstructure:OnthetopleveldrawtheX-graphandonthesecondleveltheY-graphs(see[3]formoredetails).Theobtaineddrawingre ectsthenatureofthegraphandconsiderablysimpli esitsunderstanding.AnexampleforatreeofpathsisshowninFigure1(a)withthicklinesindicatingthepaths.Thedrawings(b)and(c)aregeneratedbythealgorithmsfrom[8]and[15]respectively.

Themainproblemistodeterminewhetherornotagraphisatwo-levelclus-teredgraph.Complexityconsiderationsconcerningtwo-levelclusteredgraphsarenotknowntobeinvestigatedinliterature.Tothecontrarythereisagreatquantityofcomplexityresultsconcerningforexamplepartitioningofgraphs,seeGT11-GT16in[9],orcoveringofgraphs,seeGT17andGT18in[9].Thisresearchisstillinprogress[4,5].InfactalmostallnontrivialpartitioningandcoveringproblemsofgraphsareNP-complete.Partitioningsandcoveringsaretwo-levelclusteringsinwhichthe rstlevelgraphs(X-graphs)arearbitrary.Hence,two-levelclusteringisarestrictiveversionofpartitioningandcovering.TherestrictioncanleadtoremovingtheNP-completeness.ForexampletheproblemwhetherornotagraphisapartitionintocliquesisNP-complete(seeGT15in[9]),whereastheproblemswhetherornotagraphisapathofcliquesoralargecycleofcliquesareinP,asshownin[3].Thus,itcannotalwaysbeexpectedthateverynontrivialtwo-levelclusteringproblemisNP-complete.

Inthispaperweconsidertreesofpathsandtreesofcycles.WeshowthatgivenagraphGthequestionwhetherornotGisatreeofpaths(cycles)isNP-complete.Moreover,ifthelengthofthepaths(cycles)isbounded,wegiveapolynomialalgorithmbasedonthedynamicprogrammingtechniquetosolvethesequestions.Additionally,italsooutputssuchatreeclustering,iftheanswerispositive.AconsequenceofourresultsisthattheproblemwhetherornotagivengraphisatreeoftrianglesisinP.Thiscontraststhefactthattheproblem

上一页第2页

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email