Score Sequence Pair Problems of (r_<11>, r_<12>, r_<22>)-Tournaments : Determination of Realizability(Graph Algorithms,<Special Section>Foundations of Computer Science)

スポンサーリンク

概要

• 論文の詳細を見る

• Let G be any graph with property P (for example, general graph, directed graph, etc.) and S be nonnegative and non-decreasing integer sequence(s). The prescribed degree sequence problem is a problem to determine whether there is a graph G having S as the prescribed sequence(s) of degrees or outdegrees of the vertices. From 1950's, P has attracted wide attentions, and its many extensions have been considered. Let P be the property satisfying the following (1) and (2): (1) G is a directed graph with two disjoint vertex sets A and B. (2) There are r_<11> (r_<22>, respectively) directed edges between every pair of vertices in A(B), and r_<12> directed edges between every pair of vertex in A and vertex in B. Then G is called an (r_<11>,r_<12>,r_<22>)-tournament ("tournament", for short). The problem is called the score sequence pair problem of a "tournament" (realizable, for short). S is called a score sequence pair of a "tournament" if the answer of the problem is "yes." In this paper, we propose the characterizations of a score sequence pair of a "tournament" and an algorithm for determining in linear time whether a pair of two integer sequences is realizable or not.

• 社団法人電子情報通信学会の論文
• 2007-02-01

著者

• WATANABE Takahiro

  Graduate School of Information, Production and Systems, Waseda University

• Yoshimura Takeshi

  Graduate School Of Ips Waseda University

• TAKAHASHI Masaya

  Fukuoka Institute of Technology

• Yoshimura Takeshi

  Graduate School Of Fisheries Sciences Hokkaido University

• Takahashi Masaya

  Fukuoka Institute Of Technology:graduate School Of Waseda University

• Watanabe Takahiro

  Graduate School Of Information Production And Systems Waseda Univ.

• Yoshimura Takeshi

  Graduate School Of Waseda University

• Watanabe Takahiro

  Graduate School Of Information Production And System Waseda University

• Yoshimura Takeshi

  Graduate School of Engineering, Osaka Prefecture University, Department of Applied Materials Science, 1-1 Gakuen-cho, Sakai, Osaka 599-8531, Japan

• WATANABE TAKAHIRO

  Graduate School of Environmental Studies, Tohoku University

関連論文

• Pulsed-Laser-Deposited YMnO_3 Epitaxial Films with Square Polarization-Electric Field Hysteresis Loop and Low-Temperature Growth
• Circuit Design Optimization Using Genetic Algorithm with Parameterized Uniform Crossover
• Mixed Constrained Image Filter Design for Salt-and-Pepper Noise Reduction Using Genetic Algorithm (特集 非線形電子回路)
• Lagrangian Relaxation Based Inter-Layer Signal Via Assignment for 3-D ICs
• Max-Flow Scheduling in High-Level Synthesis(VLSI Design Technology and CAD)
• Score Sequence Pair Problems of (r_, r_, r_)-Tournaments : Determination of Realizability(Graph Algorithms,Foundations of Computer Science)
• Generation of high-density atto-second electron bunch by intense short pulse laser (特集 平成18年基礎・材料・共通部門大会)
• Nutrient Regeneration at Bottom after a Massive Spring Bloom in a Subarctic Coastal Environment, Funka Bay, Japan
• Change in the water quality in Lake Ohnuma, Hokkaido, Japan: a comparison of 1977 and 1996
• Mixed Constrained Image Filter Design for Salt-and-Pepper Noise Reduction Using Genetic Algorithm (特集 非線形電子回路)
• RC-008 Rapid Design of a Multiprocessor System for a JPEG Decoder on FPGA
• A-3-3 A Multilevel Fixed-outline Floorplanning for Large-scale IC Design
• Effects of Oxygen Annealing on Dielectric Properties of LuFeCuO4
• Redundant via Insertion : Removing Design Rule Conflicts and Balancing via Density
• Analysis before Starting an Access : A New Power-Efficient Instruction Fetch Mechanism
• A-3-2 A Parallel Routing Method using Virtual Boundary
• DS-1-3 DESIGN AND IMPLEMENTATION OF SHA-1 HASH FUNCTION USING VERILOG HDL
• Interconnect Reduction in Binding Procedure of HLS
• Interconnect Reduction in Binding Procedure of HLS
• Interconnect Reduction in Binding Procedure of HLS
• Region-Oriented Placement Algorithm for Coarse-Grained Power-Gating FPGA Architecture
• Low Power Placement and Routing for the Coarse-Grained Power Gating FPGA Architecture
• A New Recovery Mechanism in Superscalar Microprocessors by Recovering Critical Misprediction
• Floorplanning for High Utilization of Heterogeneous FPGAs
• A hybrid layer-multiplexing and pipeline architecture for efficient FPGA-based multilayer neural network
• A Behavior-based Adaptive Access-mode for Low-power Set-associative Caches in Embedded Systems
• A Behavior-based Adaptive Access-mode for Low-power Set-associative Caches in Embedded Systems
• Distribution of artificial radionuclides (^Ag, ^Te, ^Cs, ^Cs) in surface soils from Miyagi Prefecture, northeast Japan, following the 2011 Fukushima Dai-ichi nuclear power plant accident
• Pulsed-Laser-Deposited YMnO3 Epitaxial Films with Square Polarization-Electric Field Hysteresis Loop and Low-Temperature Growth
• Interconnect Reduction in Binding Procedure of HLS
• Interconnect Reduction in Binding Procedure of HLS
• Interconnect Reduction in Binding Procedure of HLS
• Floorplanning and Topology Synthesis for Application-Specific Network-on-Chips
• An Efficient Algorithm for 3D NoC Architecture Optimization
• An Efficient Algorithm for 3D NoC Architecture Optimization
• Resource-Aware Multi-Layer Floorplanning for Partially Reconfigurable FPGAs
• Network Simplex Method Based Multiple Voltage Scheduling in Power-Efficient High-Level Synthesis
• Exploration of Schedule Space by Random Walk
• A Synthesis Method of General Floating-Point Arithmetic Units by Aligned Partition
• A Sophisticated Routing Algorithm in 3D NoC with Fixed TSVs for Low Energy and Latency

もっと見る 閉じる

スポンサーリンク