Skip to main content

Research Repository

Advanced Search

Outputs (112)

Closing complexity gaps for coloring problems on H-free graphs (2012)
Presentation / Conference Contribution
Golovach, P. A., Paulusma, D., & Song, J. (2012, December). Closing complexity gaps for coloring problems on H-free graphs

If a graph G contains no subgraph isomorphic to some graph H, then G is called H-free. A coloring of a graph G = (V,E) is a mapping c: V → {1,2,…} such that no two adjacent vertices have the same color, i.e., c(u) ≠ c(v) if uv ∈ E; if |c(V)| ≤ k then... Read More about Closing complexity gaps for coloring problems on H-free graphs.

Classification of High-Dimension PDFs Using the Hungarian Algorithm (2012)
Presentation / Conference Contribution
Cope, J. S., & Remagnino, P. (2012, December). Classification of High-Dimension PDFs Using the Hungarian Algorithm. Presented at STRUCTURAL, SYNTACTIC, AND STATISTICAL PATTERN RECOGNITION Int Assoc Pattern Recognit; Int Assoc Pattern Recognit, Tech Comm 1, Stat Pattern Recognit Tech; Int Assoc Pattern Recognit, Tech Comm 2, Struct \& Syntact Pattern Recognit; Tohoku Univ; Hiroshima

Coloring graphs characterized by a forbidden subgraph (2012)
Presentation / Conference Contribution
Golovach, P. A., Paulusma, D., & Ries, B. (2012, December). Coloring graphs characterized by a forbidden subgraph

The Coloring problem is to test whether a given graph can be colored with at most k colors for some given k, such that no two adjacent vertices receive the same color. The complexity of this problem on graphs that do not contain some graph H as an in... Read More about Coloring graphs characterized by a forbidden subgraph.