MaxDDBS - MaxDDBS - Wikipedia

tento článek potřebuje víc odkazy na další články pomoci integrovat to do encyklopedie. Prosím pomozte vylepšit tento článek přidáním odkazů které jsou relevantní pro kontext v rámci stávajícího textu. (Ledna 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

The Problém s podgrafem ohraničeným maximálním stupněm a průměrem (MaxDDBS) je problém v teorie grafů.

Vzhledem k připojenému hostitelský graf G, horní mez pro titul da horní mez pro průměr k, hledáme největší podgraf S z G s maximálním stupněm maximálně d a průměr maximálně k. Tento problém se také označuje jako problém s dílčím průměrem stupně, protože obsahuje problém s průměrem stupně jako zvláštní případ (a to tím, že vezmeme dostatečně velký úplný graf jako hostitelský graf). Přestože se jedná o přirozené zobecnění problému s průměrem, MaxDDBS se začal vyšetřovat až v roce 2011, zatímco výzkum v oblasti s problémem s průměrem byl aktivní od 60. let. Pokud jde o jeho výpočetní složitost, problém je NP-hard, a ne v APX (tj. Nelze jej aproximovat v rámci konstantního faktoru v polynomiálním čase).

Reference

1. Stránka MaxDDBS v Combinatorics Wiki
2. A.Dekker, H.Perez-Roses, G.Pineda-Villavicencio a P.Watters. Subgraph s maximálním stupněm a průměrem a jeho aplikace. Journal of Mathematical Modeling and Algorithms, 2012. DOI: 10.1007 / s10852-012-9182-8
3. M.Miller, H.Perez-Roses a J.Ryan. Maximální stupeň a průměr ohraničeného podgrafu v síti. Diskrétní aplikovaná matematika, 2012. DOI: 10.1016 / j.dam.2012.03.035