Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2110.00108 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911749558501376 |
|---|---|
| author | Abrishami, Tara Chudnovsky, Maria Dibek, Cemil Vušković, Kristina |
| author_facet | Abrishami, Tara Chudnovsky, Maria Dibek, Cemil Vušković, Kristina |
| contents | We give a combinatorial polynomial-time algorithm to find a maximum weight independent set in perfect graphs of bounded degree that do not contain a prism or a hole of length four as an induced subgraph. An even pair in a graph is a pair of vertices all induced paths between which are even. An even set is a set of vertices every two of which are an even pair. We show that every perfect graph that does not contain a prism or a hole of length four as an induced subgraph has a balanced separator which is the union of a bounded number of even sets, where the bound depends only on the maximum degree of the graph. This allows us to solve the maximum weight independent set problem using the well-known submodular function minimization algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2110_00108 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Submodular functions and perfect graphs Abrishami, Tara Chudnovsky, Maria Dibek, Cemil Vušković, Kristina Combinatorics We give a combinatorial polynomial-time algorithm to find a maximum weight independent set in perfect graphs of bounded degree that do not contain a prism or a hole of length four as an induced subgraph. An even pair in a graph is a pair of vertices all induced paths between which are even. An even set is a set of vertices every two of which are an even pair. We show that every perfect graph that does not contain a prism or a hole of length four as an induced subgraph has a balanced separator which is the union of a bounded number of even sets, where the bound depends only on the maximum degree of the graph. This allows us to solve the maximum weight independent set problem using the well-known submodular function minimization algorithm. |
| title | Submodular functions and perfect graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2110.00108 |