简介：Algorithmsusedindataminingandbioinformaticshavetodealwithhugeamountofdataefficiently.Inmanyapplications,thedataaresupposedtohaveexplicitorimplicitstructures.Todevelopefficientalgorithmsforsuchdata,wehavetoproposepossiblestructuremodelsandtestifthemodelsarefeasible.Hence,itisimportanttomakeacompactmodelforstructureddata,andenumerateallinstancesefficiently.Therearefewgraphclassesbesidestreesthatcanbeusedforamodel.Inthispaper,weinvestigatedistance-hereditarygraphs.Thisclassofgraphsconsistsofisometricgraphsandhencecontainstreesandcographs.First,acanonicalandcompacttreerepresentationoftheclassisproposed.Thetreerepresentationcanbeconstructedinlineartimebyusingprefixtrees.Usually,prefixtreesareusedtomaintainasetofstrings.Inouralgorithm,theprefixtreesareusedtomaintaintheneighborhoodofvertices,whichisanewapproachunlikethelexicographicallybreadth-firstsearchusedinotherstudies.Basedonthecanonicaltreerepresentation,efficientalgorithmsforthedistance-hereditarygraphsareproposed,includinglineartimealgorithmsforgraphrecognitionandgraphisomorphismandanefficientenumerationalgorithm.Anefficientcodingforthetreerepresentationisalsopresented;itrequires[3.59n]bitsforadistance-hereditarygraphofnverticesand3nbitsforacograph.Theresultsofcodingimprovepreviouslyknownupperbounds(bothare2~(O(nlogn)))ofthenumberofdistance-hereditarygraphsandcographsto2~([3.59n])and2~(3n),respectively.