An On-line competitive algorithm for coloring bipartite graphs without long induced paths
| dc.contributor.author | Micek, Piotr | |
| dc.contributor.author | Wiechert, Veit | |
| dc.date.accessioned | 2017-08-29T07:24:32Z | |
| dc.date.available | 2017-08-29T07:24:32Z | |
| dc.date.issued | 2016 | |
| dc.description.abstract | The existence of an on-line competitive algorithm for coloring bipartite graphs is a tantalizing open problem. So far there are only partial positive results for bipartite graphs with certain small forbidden graphs as induced subgraphs. We propose an on-line competitive coloring algorithm for P9-free bipartite graphs. | en |
| dc.description.sponsorship | DFG, GRK 1408, Methoden für diskrete Strukturen | en |
| dc.identifier.eissn | 1432-0541 | |
| dc.identifier.issn | 0178-4617 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/6664 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-6105 | |
| dc.language.iso | en | |
| dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | |
| dc.subject.ddc | 511 Allgemeine mathematische Prinzipien | |
| dc.subject.ddc | 004 Datenverarbeitung; Informatik | |
| dc.subject.ddc | 510 Mathematik | |
| dc.subject.other | on-line algorithm | en |
| dc.subject.other | graph coloring | en |
| dc.subject.other | bipartite graphs | en |
| dc.title | An On-line competitive algorithm for coloring bipartite graphs without long induced paths | en |
| dc.type | Article | |
| dc.type.version | publishedVersion | |
| dcterms.bibliographicCitation.doi | 10.1007/s00453-016-0130-2 | |
| dcterms.bibliographicCitation.issue | 4 | |
| dcterms.bibliographicCitation.journaltitle | Algorithmica | |
| dcterms.bibliographicCitation.originalpublishername | Springer | |
| dcterms.bibliographicCitation.originalpublisherplace | New York, NY | |
| dcterms.bibliographicCitation.pageend | 1070 | |
| dcterms.bibliographicCitation.pagestart | 1060 | |
| dcterms.bibliographicCitation.volume | 77 | |
| tub.accessrights.dnb | free | |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik::FG Diskrete Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.group | FG Diskrete Mathematik | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin |
Files
Original bundle
1 - 1 of 1
Loading…
- Name:
- 10.1007_s00453-016-0130-2.pdf
- Size:
- 513.29 KB
- Format:
- Adobe Portable Document Format