This paper presents an efficient algorithm to generate all (unordered) rooted trees with exactly vertices including exactly k leaves. There are known results on efficient enumerations of some classes of graphs embedde...
详细信息
This paper presents an efficient algorithm to generate all (unordered) rooted trees with exactly vertices including exactly k leaves. There are known results on efficient enumerations of some classes of graphs embedded on a plane, for instance, biconnected and triconnected triangulations [3], [6], and floorplans [4]. On the other hand, it is difficult to enumerate a class of graphs without a fixed embedding. The paper is on enumeration of rooted trees without a fixed embedding. We already proposed an algorithm to generate all "ordered" trees with 17 vertices including k leaves [11], while the algorithm cannot seem to efficiently generate all (unordered) rooted trees with it vertices including k leaves. We design a simple tree structure among such trees, then by traversing the tree structure we generate all such trees in constant time per tree in the worst case. By repeatedly applying the algorithm for each k = 1, 2, . . . , n - 1, we can also generate all rooted trees with exactly n vertices.
A graph is P-5-free when it does not contain a P-5 (that is, a path with five vertices) as an induced subgraph. The class of P-5-free graphs is of particular interest, especially with respect to the still unknown comp...
详细信息
A graph is P-5-free when it does not contain a P-5 (that is, a path with five vertices) as an induced subgraph. The class of P-5-free graphs is of particular interest, especially with respect to the still unknown complexity status of the maximum stable set problem in that class. We investigate the class of 3-colorable P-5-free graphs. We give a complete description of the structure of those graphs and derive a linear-time algorithm that tests membership in this class. Moreover, the algorithm is able to find a maximum weight stable set of a 3-colorable P-5-free graph in linear time.
We study the problem of reconfiguring one list edge-coloring of a graph into another list edge-coloring by changing only one edge color assignment at a time, while at all times maintaining a list edge-coloring, given ...
详细信息
We study the problem of reconfiguring one list edge-coloring of a graph into another list edge-coloring by changing only one edge color assignment at a time, while at all times maintaining a list edge-coloring, given a list of allowed colors for each edge. Ito, Kaminski and Demaine gave a sufficient condition so that any list edge-coloring of a tree can be transformed into any other. In this paper, we give a new sufficient condition which improves the known one. Our sufficient condition is best possible in some sense. The proof is constructive, and yields a polynomial-time algorithm that finds a transformation between two given list edge-colorings of a tree with n vertices via O(n(2)) recoloring steps. We remark that the upper bound O(n(2)) on the number of recoloring steps is tight, because there is an infinite family of instances on paths that satisfy our sufficient condition and whose reconfiguration requires Omega(n(2)) recoloring steps.
Given a graph G and p is an element of N, a proper n-[p]coloring is a mapping f : V (G) -> 2((1....,n)) such that vertical bar f(v)vertical bar = p for any vertex v is an element of V (G) and f(v) boolean AND (u) =...
详细信息
Given a graph G and p is an element of N, a proper n-[p]coloring is a mapping f : V (G) -> 2((1....,n)) such that vertical bar f(v)vertical bar = p for any vertex v is an element of V (G) and f(v) boolean AND (u) = (sic) for any pair of adjacent vertices u and v. An n-[p]coloring is a special case of a multicoloring. Finding a multicoloring of induced subgraphs of the triangular lattice (called hexagonal graphs) has important applications in cellular networks. In this article we provide an algorithm to find a 7-[3]coloring of triangle-free hexagonal graphs in linear time, without using the fourcolor theorem, which solves the open problem stated by Sau. Snarl and Zerovnik (2011) and improves the result of Sudeep and Vishwanathan (2005), who proved the existence of a 14-[6]coloring. (C) 2012 Elsevier B.V. All rights reserved.
Social tagging systems have gained increasing popularity as a method of annotating and categorizing a wide range of different web resources. Web search that utilizes social tagging data suffers from an extreme example...
详细信息
Social tagging systems have gained increasing popularity as a method of annotating and categorizing a wide range of different web resources. Web search that utilizes social tagging data suffers from an extreme example of the vocabulary mismatch problem encountered in traditional information retrieval (IR). This is due to the personalized, unrestricted vocabulary that users choose to describe and tag each resource. Previous research has proposed the utilization of query expansion to deal with search in this rather complicated space. However, non-personalized approaches based on relevance feedback and personalized approaches based on co-occurrence statistics only showed limited improvements. This paper proposes a novel query expansion framework based on individual user profiles mined from the annotations and resources the user has marked. The underlying theory is to regularize the smoothness of word associations over a connected graph using a regularizer function on terms extracted from top-ranked documents. The intuition behind the model is the prior assumption of term consistency: the most appropriate expansion terms for a query are likely to be associated with, and influenced by terms extracted from the documents ranked highly for the initial query. The framework also simultaneously incorporates annotations and web documents through a Tag-Topic model in a latent graph. The experimental results suggest that the proposed personalized query expansion method can produce better results than both the classical non-personalized search approach and other personalized query expansion methods. Hence, the proposed approach significantly benefits personalized web search by leveraging users' social media data.
A (p, q)-total labeling of a graph G is an assignment f from the vertex set V (G) and the edge set E(G) to the set of nonnegative integers such that left perpendicularf(x) - f (y)right perpendicular >= p if x is a ...
详细信息
A (p, q)-total labeling of a graph G is an assignment f from the vertex set V (G) and the edge set E(G) to the set of nonnegative integers such that left perpendicularf(x) - f (y)right perpendicular >= p if x is a vertex and y is an edge incident to x, and left perpendicularf(x) - f (y)right perpendicular >= q if x and y are a pair of adjacent vertices or a pair of adjacent edges, for all x and y in V(G) U E(G). A k-(p, q)-total labeling is a (p, q)-total labeling f : V (G) boolean OR E(G) -> {0, ..., k}, and the (p, q)-total labeling problem asks the minimum k, which we denote by Apl.q (G), among all possible assignments. In this paper, we first give new upper and lower bounds on lambda(T)(p,q)(G) for some classes of graphs G, in particular, tight bounds on lambda(T)(p,q)(T) for trees T. We then show that if p <= 3q/2, the problem for trees T is linearly solvable, and completely determine lambda(T)(p,q)(T) for trees T with Delta >= 4, where Delta is the maximum degree of T. It is contrasting to the fact that the L(p, q)-labeling problem, which is a generalization of the (p, q)-total labeling problem, is NP-hard for any two positive integers p and q such that q is not a divisor of p. (C) 2012 Elsevier B.V. All rights reserved.
Given a graph G and a demand function p: V(G) -> N, a proper n-[p]coloring is a mapping f : V(G) -> 2([1.....n]) such that vertical bar f (v)vertical bar >= p(v) for every vertex v epsilon V(G) and f(v) boole...
详细信息
Given a graph G and a demand function p: V(G) -> N, a proper n-[p]coloring is a mapping f : V(G) -> 2([1.....n]) such that vertical bar f (v)vertical bar >= p(v) for every vertex v epsilon V(G) and f(v) boolean AND f(u) = emptyset for any two adjacent vertices u and v. The least integer n for which a proper n-[p]coloring exists, chi(p)(G), is called multichrornatic number of G. Finding multichromatic number of induced subgraphs of the triangular lattice (called hexagonal graphs) has applications in cellular networks. Weighted clique number of a graph G, omega(p)(G), is the maximum weight of a clique in G, where the weight of a clique is the total demand of its vertices. McDiarmid and Reed (2000) [8] conjectured that chi(p)(G) <= (9/8)omega(p)(G) + C for triangle-free hexagonal graphs, where C is some absolute constant. In this article, we provide an algorithm to find a 7-[3]coloring of triangle-free hexagonal graphs (that is, when p(v) = 3 for all v epsilon V (G)), which implies that chi(p)(G) <= (7/6)omega(p)(G) + C. Our result constitutes a shorter alternative to the inductive proof of Havet (2001) [5] and improves the short proof of Sudeep and Vishwanathan (2005) [17], who proved the existence of a 14-[6]coloring. (It has to be noted, however, that our proof makes use of the 4-color theorem.) All steps of our algorithm take time linear in vertical bar V(G)vertical bar, except for the 4-coloring of an auxiliary planar graph. The new techniques may shed some light on the conjecture of McDiarmid and Reed (2000) [8]. (C) 2011 Elsevier B.V. All rights reserved.
We develop a research community extraction algorithm from large bibliographic data, which was preliminarily reported in Horiike et al. [10] and Nakamura et al. [18]. A research community in bibliographic data is consi...
详细信息
We develop a research community extraction algorithm from large bibliographic data, which was preliminarily reported in Horiike et al. [10] and Nakamura et al. [18]. A research community in bibliographic data is considered to be a set of the linked texts holding a common topic, in other words, it is a dense subgraph embedded in the directed graph. Our method is based on the maximum flow algorithm for finding web communities by Flake et al. [5]. We propose improvements of the algorithm to select community nodes and initial seeds taking account of the restriction that any directed graph is acyclic. We examine the improved algorithm for the list of keywords frequently appearing in the bibliographic data. In addition we propose a simple method to extract characteristic keywords for deciding initial seed nodes. This method is also evaluated by experiments.
We present an approximation algorithm to find a weighted matching of a graph in the one-pass semi-streaming model. The semi-streaming model forbids random access to the input graph and restricts the memory to O(*** n)...
详细信息
We present an approximation algorithm to find a weighted matching of a graph in the one-pass semi-streaming model. The semi-streaming model forbids random access to the input graph and restricts the memory to O(*** n) bits where n denotes the number of the vertices of the input graph. We obtain an approximation ratio of 5.58 while the previously best algorithm achieves a ratio of 5.82.
The traditional network flow estimation requires monitoring on every node which consumes too much resource. So how to increase the deployment of new distributed monitors as the network expanding is becoming a new rese...
详细信息
ISBN:
(纸本)9783642275517
The traditional network flow estimation requires monitoring on every node which consumes too much resource. So how to increase the deployment of new distributed monitors as the network expanding is becoming a new research focus. This paper analyses the monitors adding mechanism and present a novel algorithm for finding candidate locations for additional deployment in the network. The algorithm is based on Apriori search method that combines with the link weight change algorithm that aims to facilitate origin-destination flow computation. We also develop the greedy algorithm with Group Betweenness Centrality(GBC) involved for the purpose of comparing. The result shows that the new algorithm need less additional monitors than greedy algorithm.
暂无评论