Search
Close this search box.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

  • Research article

Filling the Missing Names of Towns in a Map: A Graph Theoretic Approach

Frank Harary1, Aurora Morgana 2, Bruno Simeone 3
1Department of Computer Science New Mexico State University
2Dipartimento di Matematica Universita di Roma “La Sapienza”
3Dipartimento di Statistica Probabilité e Statistiche Applicate Universita di Roma “La Sapienza”
  • Published: 31/10/1997

Abstract

A map shows only the names of some (but not all) towns in a region. If for each town, the names of all neighboring towns are known, when is it possible to reconstruct from this information the missing names? We deal with a generalization of this problem to arbitrary graphs. For a graph \(G = (V, E)\) with \(n\) nodes, we give an \(O(n^3)\) algorithm to recognize those instances for which the answer is YES, as well as two characterization theorems: NO-instances are determined by the existence of a certain partition of \(V\) and YES-instances by the existence of a suitable weak order in \(V\).

Information
Guidelines
CP Initiatives
Follow CP
Facebook X-twitter Linkedin
1970-2024 CP (Manitoba, Canada) unless otherwise stated.
Citation
Frank Harary, Aurora Morgana , Bruno Simeone . Filling the Missing Names of Towns in a Map: A Graph Theoretic Approach[J], Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 025. 121-127. DOI: .