Titlebook: Combinatorial Algorithms; 27th International W Veli Mäkinen,Simon J. Puglisi,Leena Salmela Conference proceedings 2016 Springer Internation

cacophony

Online Chromatic Number is PSPACE-Completea color to each incoming vertex . so that the revealed graph is properly colored. The exact location of . in the graph . is not known to the algorithm, since it sees only previously colored neighbors of .. The . of . is the smallest number of colors such that some online algorithm is able to properl

思想

Bounded Embeddings of Graphs in the Plane the projection to the .-axis. We prove a characterization of isotopy classes of embeddings of connected graphs equipped with . in the plane containing an .-bounded embedding. Then we present an efficient algorithm, which relies on our result, for testing the existence of an .-bounded embedding if t

Hallmark

gait-cycle

灌溉

Plane Bichromatic Trees of Low Degreetite graph . contains a non-crossing spanning tree whose maximum degree is at most .; this is the best possible upper bound on the maximum degree. This solves an open problem posed by Abellanas . at the Graph Drawing Symposium, 1996.

syring

Directing Road Networks by Listing Strong Orientations direction each, so that every node can reach any other [Robbins ’39]. Using .(.) preprocessing time and space usage, it is shown that all feasible directions can be found in .(.) amortized time each. To do so, we give a new algorithm that lists all the strong orientations of an undirected connected

Anemia

Evangelism in Social Networksime-dependent) categories: ., and .. A dynamical process of information diffusion evolves among the individuals of the population according to the following rules. Initially, all individuals are agnostic. Then, a set of people is chosen from the outside and convinced to start evangelizing, i.e., to

光滑

Distance Queries in Large-Scale Fully Dynamic Complex Networkshortest-path distance queries on large-scale networks. In this paper, we propose the first dynamic algorithm to update 2-hop cover labelings for distance queries under edge removals, and show that: (i) it is efficient in terms of the number of nodes that change their distance toward some other node

GRACE

Minimax Regret 1-Median Problem in Dynamic Path Networksundirected path with positive edge lengths, uniform positive edge capacity, and nonnegative vertex supplies. Here, each vertex supply is unknown but only an interval of supply is known. A particular assignment of supply to each vertex is called a .. Given a scenario . and a sink location . in a dyna

强壮