The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem

1 February 1984

journal article
Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing

Vol. 13 (1) , 109-115
https://doi.org/10.1137/0213008

Abstract

In this paper, we use crossing number and wire area arguments to find lower bounds on the layout area and maximum edge length of a variety of computationally useful networks. In particular, we describe 1) an N-node planar graph which has layout area ...

Keywords

N-NODE PLANAR GRAPH
COMPUTATIONALLY USEFUL NETWORK
LAYOUT AREA
VERTEX-COLORING PROBLEM
WIRE AREA ARGUMENT
HAMILTONIAN PATH
MAXIMUM EDGE LENGTH
LOWER BOUND
ORIENTATION
DECISION TREE

This publication has 4 references indexed in Scilit:

On the complexity of computations under varying sets of primitives
Journal of Computer and System Sciences, 1979
A data structure for manipulating priority queues
Communications of the ACM, 1978
Depth-First Search and Linear Graph Algorithms
SIAM Journal on Computing, 1972
Efficiency of Equivalence Algorithms
Published by Springer Nature ,1972