EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Faster Graph Coloring in Polynomial Space

Serge Gaspers, Edward J. Lee

Algorithmica · 2023-02 · 85 (2) · 584-609

DOI: 10.1007/s00453-022-01034-7 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algorithmica, online erschienen am 11.10.2022. Verfasst von Serge Gaspers und 1 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 30 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Australian Research Council, Australian Government Research Training Program.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We present a polynomial-space algorithm that computes the number of independent sets of any input graph in time $$O(1.1389^n)$$ O ( 1 . 1389 n ) for graphs with maximum degree 3 and in time $$O(1.2356^n)$$ O ( 1 . 2356 n ) for general graphs, where n is the number of vertices in the input graph. Together with the inclusion-exclusion approach of Björklund, Husfeldt, and Koivisto [SIAM J. Comput. 2009], this leads to a faster polynomial-space algorithm for the graph coloring problem with running time $$O(2.2356^n)$$ O ( 2 . 2356 n ) as well as an exponential-space $$O(1.2330^n)$$ O ( 1 . 2330 n ) time algorithm for counting independent sets. Our main algorithm counts independent sets in graphs with maximum degree at most 3 and no vertex with three neighbors of degree 3. This polynomial-space algorithm is designed and analyzed using the recently introduced Separate, Measure and Conquer approach [Gaspers & Sorkin, ICALP 2015]. Using Wahlström’s compound measure approach, this improvement in running time for small degree graphs is then bootstrapped to larger degrees, giving the improvement for general graphs. Combining both approaches leads to some inflexibility in choosing vertices to branch on for the small-degree cases, which we counter by structural graph properties.

Förderung

  • Australian Research Council
  • Australian Government Research Training Program

Zitieren

APA

Gaspers, S., & Lee, E. J. (2023). Faster Graph Coloring in Polynomial Space. Algorithmica, 85(2), 584-609. https://doi.org/10.1007/s00453-022-01034-7

Vancouver

Gaspers S, Lee EJ. Faster Graph Coloring in Polynomial Space. Algorithmica. 2023;85(2):584-609. doi:10.1007/s00453-022-01034-7

BibTeX
@article{Gaspers2023,
  author = {Gaspers, Serge and Lee, Edward J.},
  title = {Faster Graph Coloring in Polynomial Space},
  journal = {Algorithmica},
  year = {2023},
  volume = {85},
  number = {2},
  pages = {584--609},
  doi = {10.1007/s00453-022-01034-7}
}
Kostenlos starten →