Artykuł w czasopiśmie
Brak miniatury
Licencja
Dostęp zamkniętyInduced subgraphs of bounded treewidth and the container method
| cris.lastimport.scopus | 2024-02-12T20:34:24Z |
| dc.abstract.en | A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By Pt we denote a path on t vertices. In this paper we give polynomial-time algorithms for the following problems: • the Maximum Weight Independent Set problem in long-hole-free graphs, and • the Feedback Vertex Set problem in P5-free graphs |
| dc.abstract.pl | W pracy pokazujemy, że wiele naturalnych problemów, w tym problem największego zbioru niezależnego czy problem najmniejszego zbioru przecinającego wszystkie cykle, można rozwiązać w czasie wielomianowym w grafach, które nie zawierają indukowanej ścieżki o 5 wierzchołkach oraz w grafach, które nie zawierają indukowanego cyklu o co najmniej 5 wierzchołkach. |
| dc.affiliation | Uniwersytet Warszawski |
| dc.conference.country | Stany Zjednoczone |
| dc.conference.datefinish | 2021-01-13 |
| dc.conference.datestart | 2021-01-10 |
| dc.conference.place | Alexandria, Virginia (Virtual Conference) |
| dc.conference.series | ACM/SIAM Symposium on Discrete Algorithms |
| dc.conference.series | ACM/SIAM Symposium on Discrete Algorithms |
| dc.conference.seriesshortcut | SODA |
| dc.conference.shortcut | SODA 2021 |
| dc.conference.weblink | https://www.siam.org/conferences/cm/conference/soda21 |
| dc.contributor.author | Pilipczuk, Marcin |
| dc.contributor.author | Rzążewski, Paweł |
| dc.contributor.author | Abrishami, Tara |
| dc.contributor.author | Seymour, Paul |
| dc.contributor.author | Chudnovsky, Maria |
| dc.date.accessioned | 2024-01-25T04:13:11Z |
| dc.date.available | 2024-01-25T04:13:11Z |
| dc.date.issued | 2021 |
| dc.description.finance | Publikacja bezkosztowa |
| dc.identifier.doi | 10.1137/1.9781611976465.116 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/109201 |
| dc.identifier.weblink | https://epubs.siam.org/doi/10.1137/1.9781611976465.116 |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.pages | 1948-1964 |
| dc.rights | ClosedAccess |
| dc.sciencecloud | nosend |
| dc.subject.en | independent set |
| dc.subject.en | feedback vertex set |
| dc.subject.en | P5-free graphs |
| dc.subject.pl | zbiór niezależny |
| dc.subject.pl | zbió przecinający wszystkie cykle |
| dc.subject.pl | grafy P5-wolne |
| dc.title | Induced subgraphs of bounded treewidth and the container method |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |