The problem that I am trying to solve is to place the vertices of a undirected, unweighted graph onto a straight line such that the arrangement has minimum bandwidth(length of the longest edge of the arrangement)
https://en.wikipedia.org/wiki/Graph_bandwidth
Each vertex of the graph has different length(integer) which means that the solution for a minimum bandwidth problem might not be the optimal solution for the problem I am trying to solve.
I was trying to see if I can model this problem as a quadratic assignment problem or job scheduling problem but so far I have not been successful.
Does this problem fall into the category of any standard combinatorial optimization problem?Is there an approximation algorithm for this (Minimum graph bandwidth problem is NP hard)?
Please check this:
https://core.ac.uk/download/pdf/62920813.pdf
http://www.math.ucsd.edu/~fan/mypaps/fanpap/86log.PDF
http://www.math.ucsd.edu/~ronspubs/78_10_bandwidth.pdf
https://link.springer.com/content/pdf/10.1007%2FBF01928924.pdf
- Badges
- Science topic
- Similar topics
- Social Science