A subpolynomial approximation algorithm for graph crossing number in low-degree graphs.
Julia ChuzhoyZihan TanPublished in: STOC (2022)
Keyphrases
- polynomial time complexity
- random graphs
- undirected graph
- low degree
- computational complexity
- cost function
- graph structure
- graph construction
- learning algorithm
- subgraph isomorphism
- graph clustering
- finding the shortest path
- optimal solution
- weighted graph
- worst case
- objective function
- spanning tree
- np hard
- machine learning