文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 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-Clustering

Problems

FalkSchreiber andKonstantinosSkodinis

UniversityofPassau,

94032Passau,Germany

{schreiber,skodinis}@informatik.uni-passau.de

AbstractAgraphisatreeofpaths(cycles),ifitsvertexsetcanbepar-titionedintoclusters,suchthateachclusterinducesasimplepath(cycle),andtheclustersformatree.Ourmainresultstatesthattheproblemwhetherornotagivengraphisatreeofpaths(cycles)isNP-complete.Moreover,ifthelengthofthepaths(cycles)isboundedbyaconstant,theproblemisinP.

1Introduction

Graphdrawingde nesoneofitstasksasdrawinggraphsina’nice’and’un-derstandable’way.Butthemeaningofthenotions’nice’and’understandable’dependsonthepointofview;thereisnouniversalde nitionofa’good’graphlayout.

Oneapproachtoproduceexpressivedrawingsareclusteringtechniques[6,7,14].ClusteringisapartitioningofthevertexsetofagraphGintosmallersetscalledclusters,whichsatisfycertaincriteria.DrawinggraphsaccordingtosuchaclusteringappearsinmanyapplicationareasasVLSIdesign,softwareengineering,andknowledgerepresentation.Themainproblemremainsto ndthecorrespondingclusters.UnfortunatelyingeneralthisproblemisNP-hard.However,iftheclustersareknown,’nice’and’understandable’graphdrawingscanoftenbeconstructede ciently.

Inthispaperwedealwithcertaingraphclassescalledtwo-levelclusteredgraphsintroducedbyBrandenburg[3].Givensuchagraphoneisinterestedindrawingswhichmakeitsstructuretransparent,especiallyifthegraphishuge.Intuitively,giventwographclassesX(level1)andY(level2),agraphGisanX-graphofY-graphs(XofYgraph)iftheverticesofGcanbepartitionedintoclusters,suchthat(i)everyclusterinducesagraphofclassYinGand(ii)theclustersformagraphofclassXinG.TheX-graphisobtainedfromGbyshrinking rsttheclustersintosingleverticesandthenthemultipleedgesintooneedge.Examplesarepathsofpaths,pathsofcliques,treesofpaths,trees

TheworkoftheauthorwassupportedbytheGermanResearchAssociation(DFG)grantBR83576-3TheworkoftheauthorwassupportedbytheGermanResearchAssociation(DFG)grantBR835/7-1

S.H.Whitesides(Ed.):GD’98,LNCS1547,pp.288–301,1998.

cSpringer-VerlagBerlinHeidelberg1998

第1页

热门文档

相关文档

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