The wikipedia article mentions:

For graphs of bounded clique-width, the longest path can also be solved by a polynomial time dynamic programming algorithm.

However there are no references and I wasn't able to find anything relevant in literature. Nor was I able to come up with a naive algorithm that would achieve this.

Would appreciate some pointers. If it's important for the algorithm -- I do have constructions of the graphs in terms of the node/union/join/rename operations.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.