检索结果-内蒙古大学图书馆

Enumerating All Rooted Trees Including k Leaves

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2012年第3期E95D卷 763-768页

作者： Ishikawa, Masanobu Yamanaka, Katsuhisa Otachi, Yota Nakano, Shin-ichi Gunma Univ Dept Comp Sci Kiryu Gunma 3768515 Japan Iwate Univ Dept Elect Engn & Comp Sci Morioka Iwate 0208551 Japan Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

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.

关键词： graph algorithm enumeration rooted tree family tree

来源：评论

学校读者我要写书评

暂无评论

ON 3-COLORABLE P₅-FREE graphS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2012年第4期26卷 1682-1708页

作者： Maffray, Frederic Morel, Gregory CNRS Lab G SCOP F-38031 Grenoble France UJF Grenoble 1 Lab G SCOP F-38031 Grenoble France

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.

关键词： graph algorithm structure theorem stability P-5-free graphs

来源：评论

学校读者我要写书评

暂无评论

An Improved Sufficient Condition Tor Reconfiguration of List Edge-Colorings in a Tree

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2012年第3期E95D卷 737-745页

作者： Ito, Takehiro Kawamura, Kazuto Zhou, Xiao Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

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.

关键词： graph algorithm list edge-coloring reachability on solution space reconfiguration problem tree

来源：评论

学校读者我要写书评

暂无评论

A linear time algorithm for 7-coloring triangle-free hexagonal graphs

引用

INFORMATION PROCESSING LETTERS 2012年第14-15期112卷 567-571页

作者： Sparl, Petra Witkowski, Rafal Zerovnik, Janez Inst Math Phys & Mech Ljubljana Slovenia Univ Maribor Fac Org Sci SI-4000 Kranj Slovenia Adam Mickiewicz Univ Fac Math & Comp Sci Poznan Poland Univ Ljubljana Fac Mech Engn SI-1000 Ljubljana Slovenia

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.

关键词： graph algorithm Approximation algorithm Multicoloring Frequency planning Hexagonal graph

来源：评论

学校读者我要写书评

暂无评论

Improving search via personalized query expansion using social media

引用

INFORMATION RETRIEVAL 2012年第3-4期15卷 218-242页

作者： Zhou, Dong Lawless, Seamus Wade, Vincent Trinity Coll Dublin Sch Comp Sci & Stat Knowledge & Data Engn Grp Ctr Next Generat Localisat Dublin 2 Ireland

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.

关键词： Personalization Query expansion Web search Social media Tag-Topic model graph algorithm

来源：评论

学校读者我要写书评

暂无评论

The (p, q)-total labeling problem for trees

引用

DISCRETE MATHEMATICS 2012年第8期312卷 1407-1420页

作者： Hasunuma, Toru Ishii, Toshimasa Ono, Hirotaka Uno, Yushi Otani Univ Commerce Dept Informat & Management Sci Otaru Hokkaido 0478501 Japan Univ Tokushima Dept Math & Nat Sci Tokushima 7708502 Japan Kyushu Univ Dept Econ Engn Fukuoka 8128581 Japan Osaka Prefecture Univ Dept Math & Informat Sci Grad Sch Sci Sakai Osaka 5998531 Japan

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.

关键词： (p, q)-total labeling L(p, q)-labeling Tree graph algorithm Distance constrained labeling

来源：评论

学校读者我要写书评

暂无评论

Simpler multicoloring of triangle-free hexagonal graphs

引用

DISCRETE MATHEMATICS 2012年第1期312卷 181-187页

作者： Sau, Ignasi Sparl, Petra Zerovnik, Janez Univ Ljubljana FS Ljubljana 1000 Slovenia CNRS LIRMM F-34095 Montpellier 5 France Univ Maribor FOV SI-4000 Kranj Slovenia IMFM Ljubljana Slovenia

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.

关键词： graph algorithm Approximation algorithm graph coloring Frequency planning Cellular networks

来源：评论

学校读者我要写书评

暂无评论

Extracting research communities from bibliographic data

引用

INTERNATIONAL JOURNAL OF KNOWLEDGE-BASED AND INTELLIGENT ENGINEERING SYSTEMS 2012年第1期16卷 25-34页

作者： Nakamura, Yushi Horiike, Toshihiko Kuboyama, Tetsuji Sakamoto, Hiroshi Kyushu Inst Technol 680-4 Kawazu Iizuka Fukuoka 8208502 Japan Gakushuin Univ Tokyo Japan JST PRESTO Kawaguchi Saitama Japan

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.

关键词： Community extraction graph algorithm information extraction

来源：评论

学校读者我要写书评

暂无评论

Weighted Matching in the Semi-Streaming Model

引用

algorithmICA 2012年第1-2期62卷 1-20页

作者： Zelke, Mariano Goethe Univ Frankfurt Inst Informat D-60054 Frankfurt Germany

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.

关键词： Semi-streaming algorithm Approximation algorithm Matching graph algorithm

来源：评论

学校读者我要写书评

暂无评论

A Novel Method for Origin-Destination Flow Computation Based on Distributed Network Monitoring

A Novel Method for Origin-Destination Flow Computation Based...

引用

International Conference on Frontiers in Computer Education (ICFCE 2011)

作者： Ou, Peng Li, Zhishu Lin, Xun Sichuan Univ Sch Comp Sci Chengdu 610064 Peoples R China Southwest Univ Finance Economy Sch Informat Engn Turku Finland

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.

关键词： Group Betweenness flow estimation Network Centrality graph algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：