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
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...
20页 免费 Skodinis NP-Completeness... 暂无评价 14页 免费搜你所想,读你... Practical Parallel Algorithms for Some Tree and Graph Problems byby隐藏>> ...
Skodinis NP-Completeness... 暂无评价 14页 免费...更多>>Graph clustering is the problem of ...We prove that the decision problems associated ...
Skodinis NP-Completene... 暂无评价 14页 免费 ...On #P-completeness of Some Counting Problems ... let x 2 be an encoding of the graph G = ...
Skodinis NP-Completeness... 暂无评价 14页 免费...更多>>Graph clustering is the problem of ...We prove that the decision problems associated ...
热门文档