the k-COLORING problem is to test whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. If a graph C does not contain a graph H as an induced subgraph, then C ...
详细信息
ISBN:
(纸本)9783642276590;9783642276606
the k-COLORING problem is to test whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. If a graph C does not contain a graph H as an induced subgraph, then C is called H-free. For any fixed graph H on at most 6 vertices, it is known that 3-COLORING is polynomial-time solvable on H-free graphs whenever H is a linear forest and NP-complete otherwise. By solving the missing case P-2+P-3, we prove the same result for 4-COLORING provided that H is a fixed graph on at most 5 vertices.
Quality of collective inference relational graph classifier depends on a. degree of homophily in a classified graph. If we increase homophily in the graph, the classifier would assign class-membership to the instances...
详细信息
ISBN:
(纸本)9783642112652
Quality of collective inference relational graph classifier depends on a. degree of homophily in a classified graph. If we increase homophily in the graph, the classifier would assign class-membership to the instances with reduced error rate. We propose to substitute traditionally used graph neighborhood method (based on direct neighborhood of vertex) with local graph ranking algorithm (activation spreading), which provides wider set of neighboring vertices and their weights. We demonstrate that our approach increases homophily in the graph by inferring optimal homophily distribution of a binary Simple Relational Classifier in an unweighted graph. We validate this ability also experimentally using the Social Network of the Slovak Companies dataset.
In this paper we provide several new results concerning word and matrix semigroup problems using counter automaton models. As a main result, we prove a new version of Post's correspondence problem to be undecidabl...
详细信息
ISBN:
(数字)9783540775669
ISBN:
(纸本)9783540775652
In this paper we provide several new results concerning word and matrix semigroup problems using counter automaton models. As a main result, we prove a new version of Post's correspondence problem to be undecidable and show its application to matrix semigroup problems, such as Any Diagonal Matrix Problem and Recurrent Matrix Problem. We also use infinite periodic traces in counter automaton models to show the undecidability of a new variation of the Infinite Post Correspondence Problem and Vector Ambiguity Problem for matrix semigroups.
the clique-chromatic number of a graph G = (V, E) denoted by chi(c)(G) is the smallest integer k such that there exists a partition of the vertex set of G into k subsets withthe property that no maximal clique of G i...
详细信息
ISBN:
(纸本)9783319042978;9783319042985
the clique-chromatic number of a graph G = (V, E) denoted by chi(c)(G) is the smallest integer k such that there exists a partition of the vertex set of G into k subsets withthe property that no maximal clique of G is contained in any of the subsets. Such a partition is called a k-clique-colouring of G. Recently Marx proved that deciding whether a graph admits a k-clique-colouring is Sigma(p)(2)-complete for every fixed k >= 2. Our main results are an O*(2(n)) time inclusion-exclusion algorithm to compute chi(c)(G) exactly, and a branching algorithm to decide whether a graph of bounded clique-size admits a 2-clique-colouring which runs in time O*(lambda(n)) for some lambda < 2.
the transitions of a stateless automaton do not depend on internal states but. solely on the symbols currently scanned by its heads accessing the input. or memory. We investigate stateless deterministic restarting aut...
详细信息
ISBN:
(纸本)9783540958901
the transitions of a stateless automaton do not depend on internal states but. solely on the symbols currently scanned by its heads accessing the input. or memory. We investigate stateless deterministic restarting automata that, after executing a rewrite step, Continue to read their tape before. performing a restart. Even the weakest class thus obtained contains the regular languages properly. the relations between different classes of stateless automata as well as between stateless automata and the corresponding types of automata with states are investigated, and it is shown that the language classes defined by the various types of deterministic stateless restarting automata without Auxiliary symbols are anti-AFLs that are not even closed under reversal.
Withthe progress of science and technology, computer technology and virtual reality technology have made rapid progress. therefore, virtual experiment technology has been developing rapidly withthe help of it. Becau...
详细信息
ISBN:
(纸本)9781538612446
Withthe progress of science and technology, computer technology and virtual reality technology have made rapid progress. therefore, virtual experiment technology has been developing rapidly withthe help of it. Because of the shortage and safety of the currentcomputer hardware assembly experimental equipment, this thesis aims to study the computer hardware assembly virtual experiment based on 3ds Maxand Virtools technology. In order to achieve real results of experiment we apply a real hardware laboratory scene in a computer simulation and increase the interaction function. the development of this experiment will not only effectively solve the problems of equipment shortage, loss and safety in computer hardware assembly experiment, but also enrich the auxiliary means of education and teaching so that put forward a new attempt for the transformation of traditional laboratories.
this article presents additional necessary measures that enable us to use Pict as an object-capability programing language. It is desirable to be able to assess the worst possible threat that we-users-risk if we run a...
详细信息
ISBN:
(数字)9783540775669
ISBN:
(纸本)9783540775652
this article presents additional necessary measures that enable us to use Pict as an object-capability programing language. It is desirable to be able to assess the worst possible threat that we-users-risk if we run a given program. If we know the threat, we are able to decide whether or not we are willing to risk running the program. the cost of a security audit that reveals such an assessment will be non-zero but it need not to be directly dependent on the size of the whole original program. It is possible to write programs in such a way that this analysis can be reliably performed on a fraction of the original program-on the trusted computing base. this technique does not always give the most accurate assessment but it gives sound and interesting assessment relatively cheaply. It does not prevent usage of other techniques that can further refine the initial assessment.
Cooperation in information retrieval contexts can be used to share query results inside groups of individuals with common objectives, provided that all of them are aware of each other. the strength of the social relat...
详细信息
this book constitutes the refereed proceedings of the 35thconference on currenttrends in theory and practice of computerscience, SOFSEM 2009, held in pindleruv Mln, Czech Republic, in January 2009. the 49 revised f...
ISBN:
(数字)9783540958918
ISBN:
(纸本)9783540958901
this book constitutes the refereed proceedings of the 35thconference on currenttrends in theory and practice of computerscience, SOFSEM 2009, held in pindleruv Mln, Czech Republic, in January 2009. the 49 revised full papers, presented together with 9 invited contributions, were carefully reviewed and selected from 132 submissions. SOFSEM 2009 was organized around the following four tracks: Foundations of computerscience; theory and practice of Software Services; Game theoretic Aspects of E-commerce; and Techniques and Tools for Formal Verification.
In various Internet applications, reputation systems are typical means to collect experiences users make with each other. We present a reputation system that balances the security and privacy requirements of all users...
详细信息
ISBN:
(纸本)9783642183805
In various Internet applications, reputation systems are typical means to collect experiences users make with each other. We present a reputation system that balances the security and privacy requirements of all users involed. Our system provides privacy in the form of information theoretic relationship anonymity w.r.t. users and the reputation provider. Furthermore, it preserves liveliness, i.e., all past ratings can influence the current reputation profile of a user. In addition, mutual ratings are forced to be simultaneous and self rating is prevented, which enforces fairness. What is more, without performing mock interactions-even if all users are colluding-users cannot forge ratings. As far as we know, this is the first protocol proposed that fulfills all these properties simultaneously.
暂无评论