ALL libraries (COBIB.SI union bibliographic/catalogue database)
13.
Approximation algorithms via contraction decomposition
Demaine, Erik D. ; Hajiaghayi, MohammadTaghi ; Mohar, Bojan, 1956-
V delu je dokazano, da je mogoče povezave vsakega grafa omejenega roda razbiti na vnaprej predpisano število delov ▫$(k)$▫, tako da ima kontrakcija kateregakoli od teh delov omejeno drevesno širino, ...kjer je meja odvisna le od števila ▫$k$▫. Podoben, a precej enostavnejši rezultat, je znan za operacijo odstranjevanja povezav namesto kontrakcije (Baker 1994, Eppstein 2000 in drugi). Dobljeno dekompozicijo uporabimo za razvoj zelo splošnih (meta)algoritmov. Med drugim dobimo polinomske aproksimacijske sheme (PTAS) za poljubne probleme, ki so monotoni za kontrakcijo povezav. Vsi taki problemi, ki izpolnjujejo še nekaj dodatnih pogojev, imajo PTAS za vse grafe omejenega roda. Tako dobimo na primer PTAS za uteženo obliko problema potujočega trgovca in za minimalni uteženi ▫$c$▫-povezavno-povezani podmultigraf v grafih omejenega roda, kar hkrati posploši večje število znanih algoritmov.
It was not necessary to add the material to the shelf.
Bibliographic material was successfully added on shelf.
Adding bibliographical material on shelf was not successful.
Material is already on the shelf.
Permalink
URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year
Impact factor
Edition
Category
Classification
JCR
SNIP
JCR
SNIP
JCR
SNIP
JCR
SNIP
Impact factor
Select the library membership card:
DRS,
in which the journal is indexed
Database name
Field
Year
Links to authors' personal bibliographies
Links to information on researchers in the SICRIS system
Subject headings in COBISS General List of Subject Headings
Select pickup location
The material from the parent unit is free. If the material is delivered to the pickup location from another unit, the library may charge you for this service.
