Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Strong digraphicality check #2547

Open
Tagl opened this issue Mar 26, 2024 · 0 comments
Open

Strong digraphicality check #2547

Tagl opened this issue Mar 26, 2024 · 0 comments
Labels
wishlist Feature request that has not been chosen for implementation yet; vote or comment to prioritize it!
Milestone
1.1

Comments

@Tagl
Copy link
Contributor

Tagl commented Mar 26, 2024

What is the feature or improvement you would like to see?
Given a sequence of out-degrees and in-degrees of vertices, determine whether there exists a strongly-connected directed simple graph with the given degrees.

image

The method described in the referenced paper can be implemented in linear time.

Use cases for the feature
The strong digraphicality check could be used to construct strongly-connected directed simple graphs.

References
https://www.doi.org/10.1002/jgt.22020
@szhorvat szhorvat added the wishlist Feature request that has not been chosen for implementation yet; vote or comment to prioritize it! label Apr 17, 2024
@szhorvat szhorvat added this to the 1.1 milestone Apr 17, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
wishlist Feature request that has not been chosen for implementation yet; vote or comment to prioritize it!
Projects
None yet
Milestone
1.1
Development

No branches or pull requests
2 participants
@szhorvat @Tagl