Home > Search Results: Chludil, Josef
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 2 records found  Search took 0.00 seconds. 
On-line algorithms for bipartite graph coloring
 Chludil, Josef ; Pangrác, Ondřej (advisor) ; Gavenčiak, Tomáš (referee)
Instance of the on-line graph coloring problem is a graph together with a permutation of its vertices (viewed as a linear ordering of the vertex set). The goal is to color the graph with vertices taken in the given order using the information of the subgraph induced by previous vertices. The most natural algorithm is the First Fit algorithm using in each step the first possible color. Unfortunately optimum number of colors can be linear dependent on number of vertices of graph even for bipartite graphs. On the other hand, there is an algorithm with logarithmic approximation factor for this class of graphs.
Detailed record
On-line algorithms for bipartite graph coloring
 Chludil, Josef ; Gavenčiak, Tomáš (referee) ; Pangrác, Ondřej (advisor)
Instance of the on-line graph coloring problem is a graph together with a permutation of its vertices (viewed as a linear ordering of the vertex set). The goal is to color the graph with vertices taken in the given order using the information of the subgraph induced by previous vertices. The most natural algorithm is the First Fit algorithm using in each step the first possible color. Unfortunately optimum number of colors can be linear dependent on number of vertices of graph even for bipartite graphs. On the other hand, there is an algorithm with logarithmic approximation factor for this class of graphs.
Detailed record

Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English