Isometriska subgrafer av hyperkuber, eller partiella kuber som de också kallas, är en rik klass av grafer som inkluderar median grafer, delsektionsgrafer av kompletta grafer, och klasser av grafer som uppstår i matematisk kemi och biologi. I allmänhet kan man känna igen om en graf på n hörn och m kanter är en partiell kub i O (mn) steg, snabbare igenkännande algoritmer är bara kända för median grafer. Detta papper uppvisar klasser av partiella kuber som inte är median grafer men kan kännas igen i O(m log n) steg. På väg relevant nedbrytning teorem för partiella kuber härleds, en av dem korrigera ett fel i en tidigare papper 13].
• Brešar m.fl. REF diskuterar flera andra klasser av partiella kuber som är nära relaterade till mediandiagrammen och kan kännas igen i O(m log n) tid.
Fast recognition algorithms for classes of partial cubes
{'venue': 'Discrete Applied Mathematics', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}