"FR - Francouzsk\u00E1 republika" . . . . . "12"^^ . . "K\u00E1ra, Jan" . . . . . . . . "9" . "P(1M0545), Z(MSM0021620838)" . . "On the Complexity of the Balanced Vertex Ordering Problem"@en . "We consider the problem of finding a balanced ordering of the vertices of a graph. More precisely, we want to minimise the sum, taken over all vertices $v$, of the difference between the number of neighbours to the left and right of $v$. One of our main results is to prove NP-hardness for graphs with maximum degree four. Furthermore, we prove that the problem remains NP-hard for planar graphs with maximum degree four and for 5-regular graphs. On the other hand, we introduce a polynomial time algorithm that determines whether there is a vertex ordering with total imbalance smaller than a fixed constant, and a polynomial time algorithm that determines whether a given multigraph with even degrees has an `almost balanced' ordering."@en . "RIV/00216208:11320/07:00004470" . "1;12" . "O slo\u017Eitosti probl\u00E9mu vyrovnan\u00E9ho uspo\u0159\u00E1d\u00E1n\u00ED vrchol\u016F"@cs . . "On the Complexity of the Balanced Vertex Ordering Problem" . "We consider the problem of finding a balanced ordering of the vertices of a graph. More precisely, we want to minimise the sum, taken over all vertices $v$, of the difference between the number of neighbours to the left and right of $v$. One of our main results is to prove NP-hardness for graphs with maximum degree four. Furthermore, we prove that the problem remains NP-hard for planar graphs with maximum degree four and for 5-regular graphs. On the other hand, we introduce a polynomial time algorithm that determines whether there is a vertex ordering with total imbalance smaller than a fixed constant, and a polynomial time algorithm that determines whether a given multigraph with even degrees has an `almost balanced' ordering." . "439333" . "RIV/00216208:11320/07:00004470!RIV08-MSM-11320___" . "3"^^ . "Complexity; Balanced; Vertex; Ordering; Problem"@en . "Uva\u017Eujeme probl\u00E9m nalezen\u00ED vyrovnan\u00E9ho uspo\u0159\u00E1d\u00E1n\u00ED vrchol\u016F grafu. P\u0159esn\u011Bji chceme minimalizovat sou\u010Det p\u0159es v\u0161echny vrcholy $v$ z rozd\u00EDlu po\u010Dtu lev\u00FDch a prav\u00FDch soused\u016F $v$. Jeden z na\u0161ich hlavn\u00EDch v\u00FDsledk\u016F je d\u016Fkaz NP-\u00FAplnosti pro rovinn\u00E9 grafy s maxim\u00E1ln\u00EDm stupn\u011Bm 4 a pro 5-regul\u00E1rn\u00ED grafy. Na druh\u00E9 stran\u011B uk\u00E1\u017Eeme algoritmus b\u011B\u017E\u00EDc\u00ED v polynomi\u00E1ln\u00EDm \u010Dase, kter\u00FD ur\u010D\u00ED, zda existuje uspo\u0159\u00E1d\u00E1n\u00ED vrchol\u016F s nevyv\u00E1\u017Eenost\u00ED men\u0161\u00ED ne\u017E dan\u00E1 konstanta nebo zda dan\u00FD multigraf se sud\u00FDmi stupni m\u00E1 't\u00E9m\u011B\u0159 vyv\u00E1\u017Een\u00E9' uspo\u0159\u00E1d\u00E1n\u00ED."@cs . . . "1" . "Kratochv\u00EDl, Jan" . "O slo\u017Eitosti probl\u00E9mu vyrovnan\u00E9ho uspo\u0159\u00E1d\u00E1n\u00ED vrchol\u016F"@cs . . . . "1365-8050" . "2"^^ . "On the Complexity of the Balanced Vertex Ordering Problem" . . "[ED00DE774C72]" . "Discrete Mathematics and Theoretical Computer Science" . "On the Complexity of the Balanced Vertex Ordering Problem"@en . "11320" .