KIEV, July 3 - President Petro Poroshenko won Parliament's approval on Thursday to shake up the leadership of the armed forces as they struggle to end a rebellion by pro-Russian separatists, Reuters reported.

Parliament endorsed Colonel-General Valery Heletey as defense minister after hearing Poroshenko describe the 46-year-old as a man "who will work day and night for restoring the military capability of our armed forces." He also named a new chief of the general staff.

Poroshenko took office last month with the country in crisis, as two eastern regions press demands to break away and join Russia, following the example of Crimea earlier this year.

After months of unsuccessful attempts to quash the uprising, he wants to sharpen the army's effectiveness while exploring diplomatic options to end the crisis, which has revived East-West tensions in ways reminiscent of the Cold War.

Poroshenko on Monday rejected a further extension of a 10-day unilateral ceasefire in the east, where the government says 200 service personnel have been killed since the start of the conflict, as well as hundreds of civilians and rebels.

In a telephone conversation with U.S. Vice President Joe Biden, Poroshenko repeated a promise that Kiev could return to the ceasefire, on three conditions.

A statement on his website said he wanted assurances on a 'bilateral' truce, the release of hostages, and the deployment of international monitors to check Ukraine's porous border with Russia. Moscow denies Ukraine's charges that it is letting fighters and weapons cross into the east of the country.

In Berlin on Wednesday the foreign ministers of Russia and Ukraine, after talks with German and French ministers, supported a further meeting of a "contact group" involving separatist leaders and aimed at trying to work out conditions for a more lasting ceasefire.

The group includes a former president of Ukraine, who is informally representing Kiev, Moscow's ambassador to Kiev, and a high-ranking official from the Organization for Security and Cooperation in Europe.

It should meet "no later than July 5th with the goal of reaching an unconditional and mutually agreed sustainable ceasefire", a document agreed by the four ministers said.

French President Francois Hollande and German Chancellor Angela Merkel urged Russian President Vladimir Putin on Thursday to encourage the separatists to reach an agreement with the Ukrainian authorities, the French president's office said.

Poroshenko, looking solemn and at times striking the table with his hand to make a point, did not mention the Berlin talks or the agreement on a possible new ceasefire, but put the emphasis instead on the need for a strong, reformed army to defend Ukraine.

Heletey, who will replace acting defense minister Mykhaylo Koval, would enact reforms to build an army which would deter anybody "from planning aggression" against Ukraine, he said.

The new head of the general staff, 52-year-old Lieutenant-General Viktor Muzhenko, was until recently a top official in the "anti-terrorist operation" grouping the army and other security bodies in the drive against the rebels.

Though Poroshenko won backing on the military shake-up, a debate on "decentralization" proposals for the regions, which is part of his peace plan, ran into trouble when a key coalition partner came out against them.

The Batkivshchyna party, a key coalition partner whose support Poroshenko requires, criticized the plan and further debate on it was postponed. (rt/ez)