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

28th International Conference on VLSI Design (VLSID) / 14th International Conference on Embedded Systems

作者： Schonborn, Eleonora Datta, Kamalika Wille, Robert Sengupta, Indranil Rahaman, Hafizur Drechsler, Rolf Univ Bremen Inst Comp Sci D-28359 Bremen Germany Natl Inst Technol Shillong 793003 Meghalaya India DFKI GmbH Cyber Phys Syst D-28359 Bremen Germany Indian Inst Technol Dept Comp Sci & Engn Kharagpur 721301 W Bengal India Bengal Engn & Sci Univ Dept Informat Technol Sibpur 711103 Howrah India

ISBN: (纸本)9781479966585

With the advancements in fabrication technology and the emergence of very high performance systems in VLSI, the interest for optical interconnects and optical functional on-chip units increased significantly. Mach-Zehnder Interferometer (MZI) switches based on Semiconductor Optical Amplifiers (SOAs) have been used as optical building blocks and allowed the synthesis of important Boolean functions such as multiplexers or adders. However, no automatic synthesis approach for arbitrary Boolean functions has been proposed yet. In this work, we introduce such a scheme. For this purpose, we make use of Binary Decision Diagrams (BDDs). A technology library is proposed where all possible BDD node configurations are identified and associated with corresponding all-optical sub-circuits. This library is utilized in order to map a BDD representing an arbitrary function into an all-optical circuit using a linear-time algorithm. Experimental evaluations confirm that this leads to an efficient realization of the considered functions.

关键词： Boolean functions Mach-Zehnder interferometers VLSI adders binary decision diagrams multiplexing equipment optical interconnections semiconductor optical amplifiers BDD-based synthesis MZI Mach-Zehnder Interferometer switches SOA all-optical Mach-Zehnder interferometer circuits linear-time algorithm optical building blocks optical interconnects Data structures Libraries Logic gates Optical interconnections Optical interferometry Optical switches optical interconnections Boolean functions Semiconductor Optical Amplifier Binary decision diagrams MACH-ZEHNDER INTERFEROMETER Multiplexing equipment adders interferometry Optical interferometry Optical switches Very large scale integration Logic gates Data structures Building blocks Libraries

来源：评论

学校读者我要写书评

暂无评论

Minimum Maximal Acyclic Matching in Proper Interval Graphs 9th

Minimum Maximal Acyclic Matching in Proper Interval Graphs

引用

9th International Conference on algorithms and Discrete Applied Mathematics (CALDAM)

作者： Chaudhary, Juhi Mishra, Sounaka Panda, B. S. Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel Indian Inst Technol Madras Dept Math Chennai India Indian Inst Technol Delhi Dept Math New Delhi India

ISBN: (纸本)9783031252105;9783031252112

Given a graph G, MIN-MAX-ACY-MATCHING is the problem of finding a maximal matching M in G of minimum cardinality such that the set of M-saturated vertices induces an acyclic subgraph in G. The decision version of MIN-MAX-ACY-MATCHING is known to be NP-complete even for planar perfect elimination bipartite graphs. In this paper, we give the first positive algorithmic result for MIN-MAX-ACY-Matching by presenting a linear-time algorithm for computing a minimum cardinality maximal acyclic matching in proper interval graphs.

关键词： Matching Acyclic matching Minimum maximal acyclic matching linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

On Selecting Leaves with Disjoint Neighborhoods in Embedded Trees 1

引用

5th International Conference on 5th International Conference on algorithms and Discrete Applied Mathematics (CALDAM)

作者： Junginger, Kolja Mantas, Ioannis Papadopoulou, Evanthia USI Univ Svizzera Italiana Fac Informat Lugano Switzerland

ISBN: (数字)9783030115098

ISBN: (纸本)9783030115098;9783030115081

We present a generalization of a combinatorial result from Aggarwal, Guibas, Saxe and Shor [1] on selecting a fraction of leaves, with pairwise disjoint neighborhoods, in a tree embedded in the plane. This result has been used by linear-time algorithms to compute certain tree-like Voronoi diagrams, such as the Voronoi diagram of points in convex position. Our generalization allows that only a fraction of the tree leaves is considered: Given is a plane tree T of n leaves, m of which have been marked. Each marked leaf is associated with a neighborhood (a subtree of T) and any topologically consecutive marked leaves have disjoint neighborhoods. We show how to select in linear time a constant fraction of the marked leaves that have pairwise disjoint neighborhoods.

关键词： Tree linear-time algorithm Neighborhood Voronoi diagram

来源：评论

学校读者我要写书评

暂无评论

COMPUTING MINIMAL SPANNING SUBGRAPHS IN linear-time

引用

SIAM JOURNAL ON COMPUTING 1995年第6期24卷 1332-1358页

作者： HAN, XF KELSEN, P RAMACHANDRAN, V TARJAN, R MAX PLANCK INST INFORMAT D-66123 SAARBRUCKENGERMANY UNIV TEXAS DEPT COMP SCIAUSTINTX 78712 PRINCETON UNIV DEPT COMP SCIPRINCETONNJ 08544 NEC RES INST PRINCETONNJ 08540

Let P be a property of undirected graphs. We consider the following problem: given a graph G that has property P, find a minimal spanning subgraph of G with property P. We describe general algorithms for this problem and prove their correctness under fairly weak assumptions about P. We establish that the worst-case running time of these algorithms is Theta(m + n log n) for 2-edge-connectivity and biconnectivity where II and m denote the number of vertices and edges, respectively, in the input graph. By refining the basic algorithms we obtain the first linear time algorithms for computing a minimal 2-edge-connected spanning subgraph and for computing a minimal biconnected spanning subgraph. We also devise general algorithms for computing a minimal spanning subgraph in directed graphs. These algorithms allow us to simplify an earlier algorithm of Gibbons, Karp, Ramachandran, Soroker, and Tarjan for computing a minimal strongly connected spanning subgraph. We also provide the first tight analysis of the latter algorithm, showing that its worst-case time complexity is Theta(m + n log n).

关键词： MINIMAL SUBGRAPHS BICONNECTIVITY 2-EDGE-CONNECTIVITY STRONG CONNECTIVITY linear-time algorithm WORST-CASE BEHAVIOR

来源：评论

学校读者我要写书评

暂无评论

Social Influence Spectrum with Guarantees: Computing More in Less time 1

引用

4th International Conference on Computational Social Network (CSoNet)

作者： Dinh, Thang Hung Nguyen Ghosh, Preetam Mayo, Michael Virginia Commonwealth Univ Dept Comp Sci Richmond VA 23284 USA US Army Engn Res & Dev Ctr Vicksburg MS 39180 USA

ISBN: (数字)9783319217864

ISBN: (纸本)9783319217864;9783319217857

Given a social network, the Influence maximization (InfMax) problem seeks a seed set of k people that maximize the expected influence for a viral marketing campaign. However, a solution for a particular seed size k is often not enough to make informed choice regarding budget and cost-effectiveness. In this paper, we propose the computation of influence spectrum (InfSpec), the maximum influence at each possible seed set' sizes (i.e. k = 1..n), thus provide optimal decision making for any range of budget or influence requirements. As none of the existing methods for InfMax are efficient enough for the task in large networks, we propose LISA, the first linear time algorithm for InfSpec (and also InfMax). LISA runs in an expected time O(is an element of(-2) (m + n)) and returns a (1 - 1/e - is an element of)-approximate influence spectrum with high probability. Using statistical decision theory, LISA has an asymptotic optimal running time (in addition to its optimal approximation guarantee). In practice, LISA also surpasses the state-of-the-art InfMax methods, taking less than 5 minutes to process a network of 41.7 million nodes and 1.5 billions edges.

关键词： Influence spectrum Influence maximization Approximation algorithm linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

The obnoxious center problem on weighted cactus graphs (Extended Abstract)

引用

Electronic Notes in Discrete Mathematics 2001年 8卷 133-136页

作者： Zmazek, Blaž Žerovnik, Janez University of Maribor FS 2000 Maribor Smetanova 17 Slovenia University of Maribor FS 2000 Maribor Smetanova 17 Slovenia

来源：评论

学校读者我要写书评

暂无评论

Edge open packing: Complexity, algorithmic aspects, and bounds

引用

THEORETICAL COMPUTER SCIENCE 2024年 1022卷

作者： Bresar, Bostjan Samadi, Babak Univ Maribor Fac Nat Sci & Math Maribor Slovenia Inst Math Phys & Mech Ljubljana Slovenia

Given a graph G, two edges e(1), e(2) is an element of E(G) said to have a common edge e not equal e(1), e(2) if e joins an endvertex of e(1) to an endvertex of e(2). A subset B subset of E(G) is an edge open packing set in G if no two edges of B have a common edge in G, and the maximum cardinality of such a set in G is called the edge open packing number, p(e)(o)(G) of G. In this paper, we prove that the decision version of the edge open packing number is NP-complete even when restricted to graphs with universal vertices, Eulerian bipartite graphs, and planar graphs with maximum degree 4, respectively. In contrast, we present a linear-time algorithm that computes the edge open packing number of a tree. We also resolve two problems posed in the seminal paper (Chelladurai et al. (2022) [5]). Notably, we characterize the graphs G that attain the upper bound p(e)(o)(G) <= |E(G)|/delta(G), and provide lower and upper bounds for the edge-deleted subgraph of a graph and establish the corresponding realization result.

关键词： Edge open packing NP-complete linear-time algorithm Independent set

来源：评论

学校读者我要写书评

暂无评论

Labeling algorithm for power domination problem of trees

引用

APPLIED MATHEMATICS AND COMPUTATION 2023年第1期457卷

作者： Lyu, Yijia East China Normal Univ High Sch 2 Shanghai Peoples R China

In this paper, the power domination problem on trees is studied and we give a linear-time algorithm to it by using the labeling method. Our algorithm is simpler and easier to understand than those in [3,7]. & COPY... 详细信息

关键词： Trees Dominating set Power domination linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Remarks on Privileged Words

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2016年第4期27卷 431-442页

作者： Forsyth, Michael Jayakumar, Amlesh Peltomaki, Jarkko Shallit, Jeffrey Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada Turku Ctr Comp Sci TUCS Turku 20520 Finland Univ Turku Dept Math & Stat Turku 20014 Finland

We discuss the notion of privileged word, recently introduced by Kellendonk, Lenz and Savinien. A word w is privileged if it is of length = 1, then w(j) is privileged for all j >= 0;(2) the language of privileged w... 详细信息

We discuss the notion of privileged word, recently introduced by Kellendonk, Lenz and Savinien. A word w is privileged if it is of length <= 1, or has a privileged border that occurs exactly twice in w. We prove the following results: (1) if w(k) is privileged for some k >= 1, then w(j) is privileged for all j >= 0;(2) the language of privileged words is not context-free;(3) there is a linear-time algorithm to check if a given word is privileged;and (4) there are at least 2(n-4)/n(2) privileged binary words of length n

关键词： Privileged word regular language linear-time algorithm context-free language enumeration

来源：评论

学校读者我要写书评

暂无评论

List-coloring clique-hypergraphs of K5-minor-free graphs strongly

引用

DISCRETE MATHEMATICS 2020年第4期343卷 111777-000页

作者： Liang, Zuosong Wu, Jianliang Shan, Erfang Qufu Normal Univ Sch Management Rizhao 276800 Peoples R China Shandong Univ Dept Math Jinan 250100 Peoples R China Shanghai Univ Sch Management Shanghai 200444 Peoples R China

Let G be a connected simple graph with at least one edge. The hypergraph H = H(G) with the same vertex set as G whose hyper-edges are the maximal cliques of G is called the clique-hypergraph of G. A list-assignment of G is a function L which assigns to each vertex v is an element of V(G) a set L(v) (called the list of v). A k-list-assignment of G is a list-assignment L such that L(v) has at least k elements for every v is an element of V(G). For a given list assignment L, a list-coloring of H(G) is a function c : V(G) -> boolean OR L-v(v) such that c(v) is an element of L(v) for every v is an element of V(G) and no hyper-edge of H(C) is monochromatic. A list-coloring of H(G) is strong if no 3-cycle of G is monochromatic. H(G) is (strongly) k-choosable if, for every k-list assignment L, there exists a (strong) list-coloring of H(G). Mohar and Skrekovski proved that the clique-hypergraphs of planar graphs are strongly 4-choosable (Electr. J. Combin. 6 (1999), #R26). In this paper we give a short proof of the result and present a linear time algorithm for the strong list-4-coloring of H(G) if G is a planar graph. In addition, we prove that H(G) is strongly 4-choosable if G is a K-5-minor-free graph, which is a generalization of their result. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Clique-hypergraph Planar graph linear-time algorithm List coloring K-5-minor

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：