38346326
The complexity of some graph colouring problems
In a binary counter made using the I2L technique, the realization of different gate types is complicated, because only NAND gates can be obtained directly. According to the invention, a particular circuit construction is indicated, which is constructed according to the I2L technique, is very simple and requires only a few gate transit times so that a comparatively high switching speed can be attained. In the circuit construction of the invention, both the flipflops and their associated combinatorial networks are fabricated in the I2L technique, using only NAND gates. Nevertheless, because of the particular circuit configuration of the invention, all of the necessary internal signals can be generated in an efficient manner.
16759367
The Complexity of Harmonious Colouring for Trees
A harmonious colouring of a simple graph G is a proper vertex colouring such that each pair of colours appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colours in such a colouring. It was shown by Hopcroft and Krishnamoorthy (1983) that the problem of determining the harmonious chromatic number of a graph is NP-hard. We show here that the problem remains hard even when restricted to trees.
122331567
A new upper bound for the harmonious chromatic number
A harmonious coloring of a simple graph G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colors in such a coloring. We obtain a new upper bound for the harmonious chromatic number of general graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 29: 257–261, 1998
40198218
The computational complexity of cordial and equitable labelling
A labelling of a simple graph G=(V,E) is an assignment f of integers to the vertices of G. Under such a labelling f, we let Vi denote the set of vertices in G that are labelled i, and let Ej={{u,v}:{u,v}∈E and |f(u)−f(v)|=j}. A k-equitable labelling of a graph G=(V,E) is a labelling f:V→{0,1,…,k−1} such that, for each 0⩽i<j⩽k−1, we have |Vi|−|Vj|∈{−1,0,1} and |Ei|−|Ej|∈{−1,0,1}. A cordial labelling of a graph G is a 2-equitable labelling of G. In this paper, we prove that the problem of deciding whether a graph G admits a cordial labelling is NP-complete, as conjectured by Kirchherr (Discrete Math. 115 (1993) 201–209). This implies that the problem of determining whether a graph G admits a k-equitable labelling is also NP-complete. A complexity result concerning another related type of labelling, known as k-cordial labelling, is also obtained.
30591318
An Algorithm for Finding Large Induced Planar Subgraphs
This paper presents an efficient algorithm that finds an induced planar subgraph of at least 3n/(d + 1) vertices in a graph of n vertices and maximum degree d. This bound is sharp for d = 3, in the sense that if ɛ > 3/4 then there are graphs of maximum degree 3 with no induced planar subgraph of at least ɛn vertices. Our performance ratios appear to be the best known for small d. For example, when d = 3, our performance ratio of at least 3/4 compares with the ratio 1/2 obtained by Halldorsson and Lau. Our algorithm builds up an induced planar subgraph by iteratively adding a new vertex to it, or swapping a vertex in it with one outside it, in such a way that the procedure is guaranteed to stop, and so as to preserve certain properties that allow its performance to be analysed. This work is related to the authors’ work on fragmentability of graphs.
6923895
Edge decomposition of complete tripartite graphs
A graph H decomposes a graph G if and only if the edges of G can be partitioned into disjoint subsets each of which induces a graph isomorphic to H. Wilson (in: C.St.J.A. Nash-Williams, J. Sheehan (Eds.), Proceedings of the Fifth British Combinatorial Conference, Aberdeen, 1975) showed, among other things, that for any graph H, there is an integer n such that H decomposes K"n, andHaggkvist (in: J. Siemons (Ed.), Surveys in Combinatories 1989, Invited papers for 12th British Combinatorial Conference, LMS Lecture Notes 141, Cambridge University Press, Cambridge, 1989, pp. 115-147) showed that for any bipartite H, there is an n such that H decomposes K"n","n. In this paper, we extend this result to tripartite graphs, by showing that for any tripartite graph H, there is an integer n such that H decomposes K"n","n","n.
109748790
Jini Example By Example
From the Publisher: 
 
Learn Jini 1.1 technology via code examples 
For the entire project lifecycle: design and coding through administration 
Coverage of ServiceUI and Surrogate Architecture 
Contains a start-to-finish application code for all aspects of Jini 
Including JavaSpaces and wrapper code 
From Keith Edwards, author of best-seller Core Jini 2nd edition 
 
 
Master Jini technology development example by example. . . . 
 
With the Jini 1.1 release, Jini network technology is rapidly maturing into a great solution for networking devices of all kinds, from wireless PDAs to servers to household appliances. Pragmatic and concise, Jini Example by Example presents techniques and real code for building reliable, high-performance Jini systems. Co-authored by Keith Edwards, author of the best-seller Core Jini 2nd edition, this book offers practical techniques and solutions you can use right now. Coverage includes: 
 
A high-level "overflight" of the philosophy and principles of Jini technology 
An introduction to the Jini Framework: program structure, clients, servers, RMI, and Jini Services 
Expert guidance and sample code for managing leasing and remote events 
A start-to-finish application case study, offering insight into how Jini systems work and what they can do 
Practical "wrapper" techniques for leveraging existing components 
Advanced JavaSpaces solutions for storing and managing the objects Jini services rely upon 
 
 
Jini Example by Example presents insiders' understanding for the entire application lifecycle: design, coding, deployment,administration, and more.
45331461
Smart homes or homes that smart?
The following is a summary of challenges for ubiquitous computing in the home that Edwards and Grinter first published in the Proceedings of Ubicomp 2001. The past few years have seen an explosion of interconnected technologies in the home. For example, Jupiter Research predicts that 28 million US households will have a home network by 2006. Devices on the home data network are typically connected to allow printer and file sharing, and to facilitate multiple broadband users. Further, paralleling this increase in the number of interconnected data-centric devices is a corresponding increase in the complexity of the home audio/visual "network." We use the term "network" here because many home entertainment systems consist of multiple components, typically connected through analog and digital cables, and controlled through a number of remotes often equal to the number of components. Increasingly, these data-centric and media-centric networks are beginning to overlap, as users want to share content across both types of devices. The complexity of the home network already presents great hurdles for current users, even including many technophilic "early adopters." These problems will only get worse as the number and types of interconnected devices in the home grow. The HCI community must address a number of challenges before these technologies will become, as Mark Weiser termed it, calming, rather than an infuriating morass of incompatibility and opaque functionality. These challenges are not purely technical. Rather, they raise cross-cutting issues in the technical, social, and design domains. For example, consider the tangle of cabling that lurks behind most home stereo installations. As confusing and opaque as this is, the move to wireless interconnec-tions between components has the potential to make usability even worse. When physical connections are present, you know what's connected to what (even if you may have difficult tracing a particular cable), and further , what can be connected to what. A system with physical connections is also relatively stable; bar kicking loose a connector, I know that the system will stay in the same configuration as when I last touched it. This is not the case when wireless technologies are used: connections are "invisible," interconnectivity can potentially change without any apparent indication of the change, and "debugging" a problem is not as simple as following a cable. Paradoxically, while it is the "invisi-bility" of wireless connections that make them appealing , it is this same invisibility that brings a new host of …