Online graph coloring against a randomized adversary

Inicio | ¿Qué es? | Contacto

English | Català

Consultar RECERCAT

Por comunidades y
colecciones Por fecha Por autores Por títulos Por temas (CDU)

Consultar departamento

Por fecha Por autores Por títulos Por temas (CDU)

Estadisticas

Del documento Todo RECERCAT

Mi RECERCAT

Entrar Alertas por correo-e

Directorio de otros repositorios

RECERCAT Principal > Universitat Politècnica de Catalunya > Documents de recerca > Visualizar documento

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/177333

dc.contributor	Universitat Politècnica de Catalunya. Departament de Matemàtiques
dc.contributor	Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions
dc.contributor.author	Burjons Pujol, Elisabet
dc.contributor.author	Hromkovic, Juraj
dc.contributor.author	Kralovic, Rastislav
dc.contributor.author	Kralovic, Richard
dc.contributor.author	Muñoz López, Francisco Javier
dc.contributor.author	Unger, Walter
dc.date	2018-06-01
dc.identifier.citation	Burjons, E. [et al.]. Online graph coloring against a randomized adversary. "International journal of foundations of computer science", 1 Juny 2018, vol. 29, núm. 4, p. 551-569.
dc.identifier.citation	0129-0541
dc.identifier.citation	10.1142/S0129054118410058
dc.identifier.uri	http://hdl.handle.net/2117/177333
dc.language.iso	eng
dc.relation	https://www.worldscientific.com/doi/abs/10.1142/S0129054118410058
dc.relation	info:eu-repo/grantAgreement/ES/1PE/TEC2013-47960-C4-1-P
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs
dc.subject	Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica aplicada a les ciències
dc.subject	Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa::Optimització
dc.subject	Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa
dc.subject	Graph theory
dc.subject	Computer software
dc.subject	Operations research
dc.subject	Information theory
dc.subject	Online computation
dc.subject	information
dc.subject	randomization
dc.subject	graph coloring
dc.subject	Grafs, Teoria de
dc.subject	Programari
dc.subject	Investigació operativa
dc.subject	Informació, Teoria de la
dc.subject	Classificació AMS::05 Combinatorics::05C Graph theory
dc.subject	Classificació AMS::68 Computer science::68N Software
dc.subject	Classificació AMS::90 Operations research, mathematical programming::90B Operations research and management science
dc.title	Online graph coloring against a randomized adversary
dc.type	info:eu-repo/semantics/submittedVersion
dc.type	info:eu-repo/semantics/article
dc.description.abstract	Electronic version of an article published as Online graph coloring against a randomized adversary. "International journal of foundations of computer science", 1 Juny 2018, vol. 29, núm. 4, p. 551-569. DOI:10.1142/S0129054118410058 © 2018 copyright World Scientific Publishing Company. https://www.worldscientific.com/doi/abs/10.1142/S0129054118410058
dc.description.abstract	We consider an online model where an adversary constructs a set of 2s instances S instead of one single instance. The algorithm knows S and the adversary will choose one instance from S at random to present to the algorithm. We further focus on adversaries that construct sets of k-chromatic instances. In this setting, we provide upper and lower bounds on the competitive ratio for the online graph coloring problem as a function of the parameters in this model. Both bounds are linear in s and matching upper and lower bound are given for a specific set of algorithms that we call “minimalistic online algorithms”.
dc.description.abstract	Peer Reviewed

Mostrar el registro sencillo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Online matching in regular bipartite graphs

Barrière Figueroa, Eulalia; Fuchs, Janosch; Muñoz Lopez, Xavier; Unger, Walter

Online coloring problem with a randomized adversary and infinite advice

Burjons Pujol, Elisabet

On the topology of 3 -manifolds and the Poincaré Conjecture

Burjons Pujol, Elisabet

Edge-partitioning regular graphs for ring traffic grooming with a priori placement od the ADMs

Muñoz López, Francisco Javier; Zhentao, Li; Sau Valls, Ignasi

Online matching in regular bipartite graphs with randomized adversary

Fàbrega Canudas, José; Muñoz López, Francisco Javier

Accesibilidad | Aviso legal | Política de Cookies | Documentos de uso interno

Coordinación

Patrocinio