EUVIMEDEUVIMED entdecken
Crossref

On Efficient Coloring of Chordless Graphs

Robert Janczewski, Michał Małafiejski

Decision Making in Manufacturing and Services · 2009

DOI: 10.7494/dmms.2009.3.2.5 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Decision Making in Manufacturing and Services, 2009. Verfasst von Robert Janczewski und 1 weiteren Autor:innen. Die Arbeit nennt 2 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We are given a simple graph G = (V, E). Any edge e ∈ E is a chord in a path P ⊆ G (cycle C ⊆ G) iff a graph obtained by joining e to path P (cycle C) has exactly two vertices of degree 3. A class of graphs without any chord in paths (cycles) we call path-chordless (cycle-chordless). We will prove that recognizing and coloring of these graphs can be done in O(n2) and O(n) time, respectively. Our study was motivated by a wide range of applications of the graph coloring problem in coding theory, time tabling and scheduling, frequency assignment, register allocation and many other areas.

Zitieren

APA

Janczewski, R., & Małafiejski, M. (2009). On Efficient Coloring of Chordless Graphs. Decision Making in Manufacturing and Services. https://doi.org/10.7494/dmms.2009.3.2.5

Vancouver

Janczewski R, Małafiejski M. On Efficient Coloring of Chordless Graphs. Decision Making in Manufacturing and Services. 2009. doi:10.7494/dmms.2009.3.2.5

BibTeX
@article{Janczewski2009,
  author = {Janczewski, Robert and Małafiejski, Michał},
  title = {On Efficient Coloring of Chordless Graphs},
  journal = {Decision Making in Manufacturing and Services},
  year = {2009},
  doi = {10.7494/dmms.2009.3.2.5}
}
Kostenlos starten →