A dynamic location problem for graphs

DOI10.1007/BF02124674zbMath0692.05055OpenAlexW1976753172WikidataQ56288399 ScholiaQ56288399MaRDI QIDQ583245

Fan R. K. Chung, Ronald L. Graham, Michael E. Saks

Publication date: 1989

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02124674

zbMATH Keywords

windexgraphsmyopicdynamic location problemon line algorithmswindow index

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Related Items

Lower bounds for on-line graph coloring, The algebra of metric betweenness. I: Subdirect representation and retraction, On the natural imprint function of a graph, Clique-gated graphs, Generalized Hamming graphs: some new results, Cartesian products of block graphs, Parametrized relocation of low‐mobility resources, Hamming polynomials and their partial derivatives, An on-line graph coloring algorithm with sublinear performance ratio, A Helly theorem in weakly modular space, Invariant Hamming graphs in infinite quasi-median graphs, A competitive analysis of the list update problem with lookahead, Retracts of infinite Hamming graphs, Skeletons, recognition algorithm and distance matrix of quasi-median graphs, A Competitive analysis of the list update problem with lookahead, Quasi-median graphs, their generalizations, and tree-like equalities, Tree-like partial Hamming graphs, Cost thresholds for dynamic resource location, The retracts of Hamming graphs, A new fixed point approach for stable networks and stable marriages, Dynamic resource location with tropical algebra, Dynamic location problems with limited look-ahead, Recognizing median graphs in subquadratic time, Decomposition and \(l_1\)-embedding of weakly median graphs, Coloring inductive graphs on-line

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Self-organizing sequential search and Hilbert's inequalities
• Median graphs and Helly hypergraphs
• Median algebras
• Vertex-to-vertex pursuit in a graph
• The smallest graph variety containing all paths
• On a class of isometric subgraphs of a graph
• Distance-preserving subgraphs of hypercubes
• Infinite median graphs, (0, 2)-graphs, and hypercubes
• Metric Ternary Distributive Semi-Lattices
• Graphs Orientable as Distributive Lattices
• On Isometric Embeddings of Graphs
• Amortized Computational Complexity
• Pursuit—Evasion games on graphs
• Join-semilattices and simple graphic algebras
• n‐cubes and median graphs
• Fixed-edge theorem for graphs with loops
• Optimal list order under partial memory constraints
• On self-organizing sequential search heuristics
• Heuristics That Dynamically Organize Data Structures
• An optimal on-line algorithm for metrical task system
• On Serial Files with Relocatable Records
• On the Addressing Problem for Loop Switching
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS