An application of graph coloring to printed circuit testing

DOI10.1109/TCS.1976.1084138zbMath0342.94021OpenAlexW2059688607MaRDI QIDQ4110937

H. C. So, Michael R. Garey, David S. Johnson

Publication date: 1976

Published in: IEEE Transactions on Circuits and Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/tcs.1976.1084138

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items

Visibility representations of boxes in 2.5 dimensions, Graph 3-coloring with a hybrid self-adaptive evolutionary algorithm, On the complexity of H-coloring, Solving graph coloring problems with the Douglas-Rachford algorithm, Rectangle-visibility representations of bipartite graphs, Determining bar-representability for ordered weighted graphs, A systematic study on meta-heuristic approaches for solving the graph coloring problem, An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm, Area, perimeter, height, and width of rectangle visibility graphs, Optimal algorithms for finding connected components of an unknown graph, New results on the robust coloring problem, Covering complete hypergraphs with cuts of minimum total size, An immune algorithm with stochastic aging and Kullback entropy for the chromatic number problem, Unnamed Item, Precoloring extension. I: Interval graphs, Some results on visibility graphs, A wide-ranging computational comparison of high-performance graph colouring algorithms, Coloring large graphs based on independent set extraction, A survey of local search methods for graph coloring, Improving the extraction and expansion method for large graph coloring, How many circuits determine an oriented matroid?, Multi-agent oriented constraint satisfaction, Covering Complete r-Graphs with Spanning Complete r-Partite r-Graphs, An adaptive, multiple restarts neural network algorithm for graph coloring, On fractional cut covers, A memetic algorithm for graph coloring, A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results, AN EXTRACTION AND EXPANSION APPROACH FOR GRAPH COLORING