Skip to content

Use knowledge of cographs to make things faster #890

@mtorpey

Description

@mtorpey

@coraaked is in the process of contributing an IsCograph function that will tell us whether a graph is a cograph or not.

In her presentation she told us some interesting stuff about trees and looking properties up, with alternative representations of cographs as trees with 1s and 0s on the nodes.

This makes me think that, if we recognise that a graph is a cograph, we may be able to take advantage of this knowledge computationally. This would be in the form of:

  • Immediate methods
  • "Set" operations called before returning from IsCograph
  • Methods that take IsCograph as a filter and do something fast that relies on cographness.

Someone should look into what mathematical facts we can say about cographs, and translate these into code where appropriate.

Metadata

Metadata

Assignees

No one assigned

    Labels

    difficulty: 3Label for feature requests that are probably rather hard

    Type

    No type

    Projects

    Status

    Unassigned

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions