Name
Abstract | ||
|---|---|---|
In the Imbalance Minimization problem we are given a graph G=(V,E) and an integer b and asked whether there is an ordering v"1...v"n of V such that the sum of the imbalance of all the vertices is at most b. The imbalance of a vertex v"i is the absolute value of the difference between the number of neighbors to the left and right of v"i. The problem is also known as the Balanced Vertex Ordering problem and it finds many applications in graph drawing. We show that this problem is fixed parameter tractable and provide an algorithm that runs in time 2^O^(^b^l^o^g^b^)@?n^O^(^1^). This resolves an open problem of Kara et al. [On the complexity of the balanced vertex ordering problem, in: COCOON, in: Lecture Notes in Comput. Sci., vol. 3595, 2005, pp. 849-858]. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.ipl.2013.06.010 | Computing and Combinatorics |
Keywords | Field | DocType |
imbalance minimization problem,open problem,integer b,graph drawing,lecture notes,graph g,absolute value,parameter tractable,balanced vertex,vertex v,balanced vertex ordering problem,parameterized complexity,algorithms | Integer,Discrete mathematics,Parameterized complexity,Combinatorics,Open problem,Vertex (geometry),Vertex (graph theory),Neighbourhood (graph theory),Vertex cover,Mathematics,Feedback vertex set | Journal |
Volume | Issue | ISSN |
113 | 19-21 | 0020-0190 |
ISBN | Citations | PageRank |
3-642-14030-0 | 2 | 0.43 |
References | Authors | |
15 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel Lokshtanov | 1 | 1438 | 110.05 |
| Neeldhara Misra | 2 | 341 | 31.42 |
| Saket Saurabh | 3 | 2023 | 179.50 |