36 research outputs found
On a reconstruction problem
No full textAbstractThis note supplements an earlier paper of this author, in which the concept of a strong k-hypomorphism between two graphs was defined (Thatte, 1990, Sectin VI). For k=1, this is just a hypomorphism. Here it is proved that strongly k-hypomorphic graphs and strongly k-edge hypomorphic directed graphs are isomorphic if k>1
A reconstruction problem related to balance equations II: The general case
No full textAbstractA modified k-deck of a graph G, first introduced in (Krasikov and Roditty, 1987), is obtained by removing k edges of G in all possible ways, and adding k (not necessarily new) edges in all possible ways. Krasikov and Roditty asked if it was possible to construct the usual k-edge deck of a graph from its modified k-deck. In (Thatte, to appear), the author solved this problem for the case when k = 1. In this paper, the problem is completely solved for arbitrary k. The proof makes use of the k-edge version of Lovász's result and the eigenvalues of certain matrix related to the Johnson graph
A versão algorítmica do Lema Local de Lovász com aplicações a problemas de coloração de grafos
No full textThe objective of this work is to present the proof of the algorithmic version of the Lovász local lema as well as an improved version of it and apply it to problems of coloring of graphs.O objetivo deste trabalho é apresentar a demonstração da versão algorítmica do lema local de Lovász bem como uma versão melhorada do mesmo e aplicá-lo a problemas de coloração de grafos
A versão algorítmica do Lema Local de Lovász com aplicações a problemas de coloração de grafos
No full textThe objective of this work is to present the proof of the algorithmic version of the Lovász local lema as well as an improved version of it and apply it to problems of coloring of graphs.O objetivo deste trabalho é apresentar a demonstração da versão algorítmica do lema local de Lovász bem como uma versão melhorada do mesmo e aplicá-lo a problemas de coloração de grafos
Fault Diagnosis of Semiconductor Random Access Memories
No full textMade available in DSpace on 2015-04-22T02:53:37Z (GMT). No. of bitstreams: 2
license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5)
B35-769.pdf: 22072178 bytes, checksum: 6d8ae34606e02a014858febbb4b36d56 (MD5)
Previous issue date: 1977-05Embargo set by: Seth Robbins for item 76376
Lift date: Forever
Reason: Restricted to UIUC communityMade available in DSpace on 2017-07-14T23:57:43Z (GMT). No. of bitstreams: 3
B35-769.pdf.txt: 88246 bytes, checksum: e6eb4632f2f2e1546024a4ecb5eccc21 (MD5)
B35-769.pdf: 23567999 bytes, checksum: 80722b6b1e9be1285263fe7b84321899 (MD5)
license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5)
Previous issue date: 1977-05Embargo set by: Seth Robbins for item 100821
Lift date: Forever
Reason: Restricted to UIUC communityOpen Restriction set for Item 100821 on 2019-11-15T17:33:23Z with date null by [email protected] Services Electronics Program / DAAB-07-72-C-0259OpenCoordinated Science Laboratory was formerly known as Control Systems Laboratory"Author name appears as ""Satish Munkund Thatte"" in front matter
Provenance-based trust for grid computing: Position Paper
No full textCurrent evolutions of Internet technology such as Web Services, ebXML, peer-to-peer and Grid computing all point to the development of large-scale open networks of diverse computing systems interacting with one another to perform tasks. Grid systems (and Web Services) are exemplary in this respect and are perhaps some of the first large-scale open computing systems to see widespread use - making them an important testing ground for problems in trust management which are likely to arise. From this perspective, today's grid architectures suffer from limitations, such as lack of a mechanism to trace results and lack of infrastructure to build up trust networks. These are important concerns in open grids, in which "community resources" are owned and managed by multiple stakeholders, and are dynamically organised in virtual organisations. Provenance enables users to trace how a particular result has been arrived at by identifying the individual services and the aggregation of services that produced such a particular output. Against this background, we present a research agenda to design, conceive and implement an industrial-strength open provenance architecture for grid systems. We motivate its use with three complex grid applications, namely aerospace engineering, organ transplant management and bioinformatics. Industrial-strength provenance support includes a scalable and secure architecture, an open proposal for standardising the protocols and data structures, a set of tools for configuring and using the provenance architecture, an open source reference implementation, and a deployment and validation in industrial context. The provision of such facilities will enrich grid capabilities by including new functionalities required for solving complex problems such as provenance data to provide complete audit trails of process execution and third-party analysis and auditing. As a result, we anticipate that a larger uptake of grid technology is likely to occur, since unprecedented possibilities will be offered to users and will give them a competitive edge
On the Boolean dimension of a graph and other related parameters
No full textWe present the Boolean dimension of a graph, we relate it with the notions of
inner, geometric and symplectic dimensions, and with the rank and minrank of a
graph. We obtain an exact formula for the Boolean dimension of a tree in terms
of a certain star decomposition. We relate the Boolean dimension with the
inversion index of a tournament.Comment: 13 pages, 2 figure
A correct proof of the McMorris–Powers’ theorem on the consensus of phylogenies
No full textAbstractMcMorris and Powers proved an Arrow-type theorem on phylogenies given as collections of quartets. There is an error in one of the main lemmas used to prove this theorem. However, this lemma (and thereby the theorem) is still true, and we provide a corrected proof
