Universal Graphs for Graphs with Bounded Path-Width

スポンサーリンク

概要

• 論文の詳細を見る

• A graph G is said to be universal for a family F of graphs if G contains every graph in F as a subgraph. A minimum universal graph for F is a universal graph for F with the minimum number of edges. This paper considers a minimum universal graph for the family F_n^k of graphs on n vertices with path-width at most k. We first show that the number of edges in a universal graph for F_n^k is at least Ω (kn log(n/k)). Next, we construct a universal graph for F_n^k with O (kn log(n/k)) edges, and show that the number of edges in a minimum universal graph for F_n^k is Θ (kn log(n/k)).

• 社団法人電子情報通信学会の論文
• 1995-04-25

著者

• Ueno S

  Department Of Communications And Integrated Systems Tokyo Institute Of Technology

• Ueno Shuichi

  Dept. Of Communications And Integrated Systems Tokyo Institute Of Technology

• Ueno Shuichi

  Tokyo Inst. Of Technol. Tokyo Jpn

• Kajitani Y

  Department Of Electrical And Electronic Engineering Tokyo Institute Of Technology

• Kajitani Yoji

  The Department Of Electrical And Electronic Engineering Tokyo Institute Of Technology

• UENO Shuichi

  Faculty of Engineering, Tokyo Institute of Technology

• Takahashi Atsushi

  Faculty of Engineering, Tokyo Institute of Technology

• Kajitani Yoji

  School of Information Science, Japan Advanced Institute of Science and Technology

• Ueno Shu-ichi

  Department Of Communications And Integrated Systems Tokyo Institute Of Technology

• Ueno Shuichi

  The Faculty Of Engineering Tokyo Institute Of Technology

• Ueno Shuichi

  Faculty Of Engineering Tokyo Institute Of Technology

• Takahashi Atsushi

  Faculty Of Engineering Tokyo Institute Of Technology

関連論文

• A-3-10 Top Layer Plating Lead Maximization for BGA Packages
• A Clustering Based Fast Clock Schedule Algorithm for Light Clock-Trees(Special Section on VLSI Design and CAD Algorithms)
• A Note on Two Problems of Nano-PLA Design
• A Note on Two Problems of Nano-PLA Design
• A Note on Two Problems of Nano-PLA Design
• A-1-28 A Note on a Problem of Nano-PLA Design
• Common coding variant in the TCF7L2 gene and study of the association with type 2 diabetes in Japanese subjects
• On the Complexity of Fault Testing for Reversible Circuits
• A-1-26 On the Complexity of Fault Testing for Reversible Circuits
• Routability Driven Via Assignment Method for 2-Layer Ball Grid Array Packages
• Positional Candidate Approach for the Gene Responsible for Benign Adult Familial Myoclonic Epilepsy
• MILP-Based Efficient Routing Method with Restricted Route Structure for 2-Layer Ball Grid Array Packages
• A-1-8 Bandwidth of Convex Bipartite Graphs
• A-1-8 Characterizations of Two-Directional Orthogonal Ray Graphs
• Orthogonal ray graphs and nano-PLA design (コンカレント工学)
• Orthogonal ray graphs and nano-PLA design (回路とシステム)
• On orthogonal ray graphs (アルゴリズム)
• On Orthogonal Ray Graphs with Applications to NanoPLA Design : Extended Abstract
• On Orthogonal Ray Graphs with Applications to NanoPLA Design : Extended Abstract
• On Orthogonal Ray Graphs with Applications to NanoPLA Design : Extended Abstract
• On the permutation routing in all-optical caterpillar networks (回路とシステム)
• On the permutation routing in all-optical caterpillar networks (コンカレント工学)
• Gate-Level Register Relocation in Generalized Synchronous Framework for Clock Period Minimization(Selected Papers from the 19th Workshop on Circuits and Systems in Karuizawa)
• Leakage Mechanism of Local Junctions Forming the Main or Tail Mode of Retention Characteristics for Dynamic Random Access Memories
• Leakage Mechanism of Local Junctions Forming Main or Tail Mode of DRAM Retention Characteristics
• On the Complexity of Embedding of Graphs into Grids with Minimum Congestion (Special Section on Discrete Mathematics and Its Applications)
• A Note on the Complexity of Scheduling for Precedence Constrained Messages in Distributed Systems(Algorithms and Data Structures)
• A Fast Longer Path Algorithm for Routing Grid with Obstacles Using Biconnectivity Based Length Upper Bound
• On the Three-Dimensional Orthogonal Drawing of Series-Parallel Graphs
• A-1-27 On the Three-Dimensional Layout of Butterfly Networks
• On the Orthogonal Drawing of Outerplanar Graphs(Graphs and Networks)
• A-1-31 A Note on Sparse Networks Tolerating Random Faults for Cycles(A-1. 回路とシステム, 基礎・境界)
• On the Orthogonal Drawing of Series-Parallel Graphs
• On the Three-Dimensional Channel Routing
• Genetic polymorphisms of serotonin and dopamine transporters in mental disorders
• Minimal Forbidden Minors for the Family of Graphs with Proper-Path-Width at Most Two
• Universal Graphs for Graphs with Bounded Path-Width
• On the Proper-Path-Decomposition of Trees
• A Linear Time Algorithm for Constructing Proper-Path-Decomposition of Width Two
• The Oct-Touched Tile : A New Architecture for Shape-Based Routing( Analog Circuit Techniques and Related Topics)
• A Device-Level Placement with Schema Based Clusters in Analog IC Layouts(Analog Layout)(VLSI Design and CAD Algorithms)
• Abstraction and Optimization of Consistent Floorplanning with Pillar Block Constraints(Floorplan)(VLSI Design and CAD Algorithms)
• A-1-25 On Efficient Universal Quantum Circuits
• Universal test sets for reversible circuits (コンカレント工学)
• Universal test sets for reversible circuits (回路とシステム)
• A-1-14 Fault Testing for Linear Reversible Circuits
• On Fault Testing for Reversible Circuits
• On the fault testing for reversible circuits (アルゴリズム)
• Optimal Time-Multiplexing in Inter-FPGA Connections for Accelerating Multi-FPGA Prototyping Systems
• Computational Complexity Analysis of Set-Bin-Packing Problem(Special Section on Discrete Mathematics and Its Applications)
• Assignment of Intervals to Parallel Tracks with Minimum Total Cross-Talk
• Routability of FPGAs with Extremal Switch-Block Structures(Special Section on Discrete Mathematics and Its Applications)
• A Note on the Circuit-switched Fixed Routing in Networks (特集 並列処理)
• A Note on the Implementation of de Bruijn Networks by the Optical Transpose Interconnection System(Graphs and Networks)
• On Two Problems of Nano-PLA Design
• CAFE Router : A Fast Connectivity Aware Multiple Nets Routing Algorithm for Routing Grid with Obstacles
• A-1-7 Universal Test Sets for Reversible Circuits
• A Fast Clock Scheduling for Peak Power Reduction in LSI
• Minimization of Delay Insertion in Clock Period Improvement in General-Synchronous Framework
• A-3-4 Optimal Register Merging Method after Register Relocation in Semi-Synchronous Framework
• An Improvement of Network-Flow Based Multi-Way Circuit Partitioning Algorithm
• An Efficient Algorithm to Extract an Optimal Sub-Circuit by the Minimum Cut
• Air-Pressure Model and Fast Algorithms for Zero-Wasted-Area Layout of General Floorplan(Special Section on Discrete Mathematics and Its Applications)
• AS-1-1 The Complexity of Fault Testing for Reversible Circuits
• A Via Assignment and Global Routing Method for 2-Layer Ball Grid Array Packages(Discrete Mathematics and Its Applications)
• Routability Driven Via Assignment and Routing for 2-Layer Ball Grid Array Packages
• Routing of Monotonic Parallel and Orthogonal Netlists for Single-Layer Ball Grid Array Packages(Physical Design,VLSI Design and CAD Algorithms)
• Clock Period Minimization Method of Semi-Synchronous Circuits by Delay Insertion(Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)
• Cost-Radius Balanced Spanning/Steiner Trees (Special Section on Discrete Mathematics and Its Applications)
• On the Complexity of Energy-Aware Mapping for NoCs (信号処理)
• On the Complexity of Energy-Aware Mapping for NoCs (回路とシステム)
• On the Complexity of Energy-Aware Mapping for NoCs (通信方式)
• Low Area Pipelined Circuits by the Replacement of Registers with Delay Elements(Circuit Synthesis,VLSI Design and CAD Algorithms)
• Multi-Clock Cycle Paths and Clock Scheduling for Reducing the Area of Pipelined Circuits(System Level Design,VLSI Design and CAD Algorithms)
• Routability Driven Via Assignment and Routing for 2-Layer Ball Grid Array Packages (デザインガイア2006--VLSI設計の新しい大地を考える研究会)
• Routability Driven Via Assignment and Routing for 2-Layer Ball Grid Array Packages (デザインガイア2006--VLSI設計の新しい大地を考える研究会)
• Derivative Coupling Meson Theory and PCAC
• Current Commutation Relation and Pion-Nucleon Scattering
• On Minimum Feedback Vertex Sets in Graphs (システム数理と応用)
• On Minimum Feedback Vertex Sets in Graphs (信号処理)
• On Minimum Feedback Vertex Sets in Graphs (VLSI設計技術)
• On Minimum Feedback Vertex Sets in Graphs (回路とシステム)
• A-1-35 Minimum Feedback Vertex Sets in Permutation Bigraphs
• The high mannose-type glycan binding lectin actinohivin : dimerization greatly improves anti-HIV activity
• Remapping and mutation analysis of benign adult familial myoclonic epilepsy in a Japanese pedigree
• On Efficient Universal Quantum Circuits (回路とシステム)
• On Efficient Universal Quantum Circuits (システム数理と応用)
• Actinohivin : specific amino acid residues essential for anti-HIV activity
• FOREWORD
• Clinical profiles of late-onset semantic dementia, compared with early-onset semantic dementia and late-onset Alzheimer's disease

もっと見る 閉じる

スポンサーリンク