Bipartition of Biconnected Graphs
スポンサーリンク
概要
- 論文の詳細を見る
We present a linear algorithm for solving bipartition problem for a biconnected graph. The bipartition problem is the following : Input : (1) an undirected graph G=(V, E) with n=|V| vertices and m=|E| edges ; (2) s_1, s_2 ∈ V, s_1 ≠ s_2 ; and (3) two natural numbers n_1, n_2 ∈ N such that n_1 + n_2 = n. Output : a partition(V_1, V_2)of vertex set V such that (a) s_1 ∈ V_1 and s_2 ∈ V_2 ; (b) |V_1| = n_1 and |V_2| = n_2 ; and (c) V_1 and V_2 induce connected subgraphs of G. Fig. 1 depicts an instance of the problem above and a solution. Clearly the problem has no solution for some graphs. Furthermore the problem determining whether theabove problem has a solution is NP-complete if G may be not biconnected [DF]. However, Gyori and Lovasz independently proved the following theorem. THEOREM 1 [Gy, Lo]. If G is k-partition problem has a solution. the k-partition problem is one to find k disjoint connected subgraphs in a graph each of which contains a specified vertex and has a specified number of vertices. Since the bipartition problem is a subproblem of k-partition problem, it necessarily has a solution if the given graph G is biconnected. Although the proof by Gyori provides a polynomial algorithm if k = 2, naive implementation of the algorithm does not run in linear time. Our algorithm is not based on the proofs but based on characteristics of a depth first search tree in a biconnected graph.
- 一般社団法人情報処理学会の論文
- 1989-10-16
著者
-
Nishizeki Takao
Tohoku Univ. Sendai‐shi Jpn
-
SUZUKI Hitoshi
Tohoku Gakuin University
-
鈴木 仁
東京慈恵会医科大学
-
Nishizeki Takao
Tohoku Univ. Sendai
-
Nishizeki Takao
Tohoku University
-
Takahashi Naomi
Tohoku University
-
Suzuki H
Laboratory Of Ecology And Genetics Graduate School Of Environmental Earth Science Hokkaido Universit
関連論文
- P-146 Y染色体の蟄居仮説 : 核型XOの2種の琉球トゲネズミに見られるY連関遺伝子のX染色体への部分転座ならびに一般的なY染色体矮小化に伴うY連関遺伝子の末端局在からの類推(ポスターセッション)
- Magnetization Process of an S = 1/2 Tetramer Chain with Ferromagnetic-Ferromagnetic-Antiferromagnetic-Antiferromagnetic Bond Alternating Interactions
- Morphological Alteration and Structure of ZnO Particles Produced in Electric Field(Condensed matter: electronic structure and electrical, magnetic, and optical properties)
- 第60回全国大会研究発表要旨 染色体の教材化(2)
- 第60回全国大会研究発表要旨 染色体の教材化(1)
- A ROBUST ENSEMBLE LEARNING USING ZERO-ONE LOSS FUNCTION
- AdaBoostを用いた顧客スコアリング
- A ROBUST BOOSTING METHOD FOR MISLABELED DATA
- 0-1損失関数を用いたロバストなブースティングの提案(データマイニング)
- ブースティングを用いたスコアリングモデルの構築(データマイニング)
- A Robust Boosting Method using Zero-one Loss Function :SNRBoost (6th Workshop on Stochastic Numerics)
- AdaBoostによる顧客スコアリング(データマイニング)
- AdaBoostのロバスト化(データ解析)
- 工程に自己相関がある場合の分散モニタリング管理図 : ブートストラップ法を用いて(投稿論文)
- List Edge-Colorings of Series-Parallel Graphs
- Linear Algorithm for Finding List Edge-Colorings of Series-Parallel Graphs (Special Issue on Selected Papers from LA Symposium)
- 哺乳類の類縁をさぐる : 比較形態からのアプローチ
- Magnetization Process of an S = 1/2 Tetramer Chain with Ferromagnetic-Ferromagnetic-Antiferromagnetic-Antiferromagnetic Bond Alternating Interactions
- LASP FAMILY PROTEINS OF INVERTEBRATES(Cell Biology and Morphology,Abstracts of papers presented at the 75^ Annual Meeting of the Zoological Society of Japan)
- Field-Induced Ferromagnetic Transition in PrInNi_4
- High-Field Magnetization of Single Crystalline TbRh_2Si_2
- Antiferromagnetic Order in Bi_4Cu_3V_2O_14 with Novel Spin Chain
- Spin-Singlet State of A_2CuB_2O_6 (A=Sr, Ba) with a Layered Structure
- S=1/2 Trimer in KBa_3Ca_4Cu_3V_7O_
- Magnetic Properties of Geometrically Frustrated System RPdAl (R = Ce and Pr)
- Successive Field Induced Magnetic Phase Trancitions of Heavy Fermion Compound CeRh_2Si_2
- 哺乳類の類縁をさぐる : 新しいアプローチの魅力
- 哺乳類の類縁をさぐる : 新しいアプローチの魅力
- 1-G-2 大規模データに対するSVRを用いたアンサンブル学習(MIS・DSS)
- Charge Segregation in the Metal-Insulator Transition of the Thiospinel Cu_Zn_xIr_2S_4 : Condensed Matter: Structure, etc.
- Chromosomal polymorphism in the gray shrew Crocidura attenuata (Mammalia : Insectivora)
- ヤケイ属リボソームDNA制限酵素切断位置の変異
- トゲネズミの分類学的研究 : I。遺伝的分化
- Novel Frustrated Spin Chain System in KCu_5V_3O_
- Geographic Patterns of Cytochrome b and Sry Gene Lineages in the Gray Red-Backed Vole Clethrionomys rufocanus from Far East Asia Including Sakhalin and Hokkaido(Phylogeny)
- Metal-Insulator Transition and Superconductivity in Spinel-Type System Cu_Zn_xIr_2S_4
- The Effect of Quadrupolar Interaction on High-Field Magnetization of PrNi_5 Single Crystal
- Sufficient Condition and Algorithm for List Total Colorings of Series-Parallel Graphs(Discrete Mathematics and Its Applications)
- Phylogeographic origin of Hokkaido house mice (Mus musculus) as indicated by maternal, paternal and biparental inheritance molecules
- Magnetic Properties of CeScSi Single Crystal
- ルポルタ-ジュ The 11th Asia Quality Symposium 1997 Tainan
- ウェーブレット変換を用いた工程異常パターンの識別
- Phylogenetic relationships among East Asian species of Crocidura (Mammalia, Insectivora) inferred from mitochondrial cytochrome b gene sequences
- Phylogenetic Relationships Within Parrots (Psittacidae) Inferred from Mitochondrial Cytochrome-b Gene Sequences(Phylogeny)
- ネズミ類に見る生物の進化と外来種問題 (特集 越境する動物たち--いま自然界に何が起こっているのか? 人間社会への/人間社会によるインパクトとは?)
- 野生哺乳類、特にネズミ類の遺伝学
- リボソームDNAの遺伝的分化 : 小型哺乳類の系統解析
- ヤマドリ属の分類学的関係
- Isolated Dimers in an Alternating Chain of BaCu2V2O8 (Proceedings of the International Conference on Strongly Correlated Electrons with Orbital Degrees of Freedom(ORBITAL2001))
- Restriction fragment length polymorphism of nuclear rDNA in Sorex caecutiens/shinto group (Eulipotyphla, Soricidae)
- Molecular phylogeny of Crocidura shrews in northeastern Asia: A special reference to specimens on Cheju Island, South Korea
- 23. ジャコウネズミCrocidura attennuataの染色体多型(日本動物分類学会第37会大会講演抄録)
- 13. ニホンジネズミの起源について(日本動物分類学会第35回大会)
- 小哺乳類ネットワークの具体的活用に向けて : そのサンプル・データ, 眠らせないで
- Ferroelectricity in Barium Sodium Tantalate Ba_2NaTa_5O_15
- Note on the Phase Diagram of Ba_2NaNb_Ta_O_
- Edge-Coloring Problems for Graphs
- イリオモテヤマネコとベンガルヤマネコ,Felis bengalensis,のrDNAの変異に基づく系統関係〔英文〕
- Partitioning a Multi-Weighted Graph to Connected Subgraphs of Almost Uniform Size(Graph Algorithms,Foundations of Computer Science)
- Algorithms for Multicolorings of Partial ★-Trees (Special Issue on Selected Papers from LA Symposium)
- Best Security Index for Digital Fingerprinting(Information Hiding, Cryptography and Information Security)
- New Security Index for Digital Fingerprinting and Its Bounds
- GaN Nanoparticle Formation in Plasma Field(Condensed Matter : Structure, Mechanical and Thermal Properties)
- Growth and the Phase Transition of Indium Sulfide Ultrafine Particle(Condensed Matter : Electronic Structure, Electrical, Magnetic and Optical Properties)
- Phase Transition Temperature of γ-Fe_2O_3 Ultrafine Particle(Cross-disciplinary Physics and Related Areas of Science and Technology)
- Structure and Thickness of Natural Oxide Layer on Ultrafine Particle
- Structure and Growth of Rod-Shaped Mn Ultrafine Particle
- ヤマドリ属の分類学的関係
- High Resolution Transmission Electron Microscopy of Structural Change in Carbon particle Carrying Pt Clusters
- Au Alloy Formation with Sn-Pb or Sn-Zn Solder Nanoparticles
- Experimental Evidence of Stability of Pt Clusters on and in Carbon Particles
- Size Control and Characteristic Growth of CdS and CdTe Ultrafine Particles in Electric Field(Condensed Matter : Electronic Structure, Electrical, Magnetic and Optical Properties)
- Pentagonal Configurartion in GaP Ultrafine Particle
- Structural Control of Silicon Oxide Particles by Oxygen Partial Pressure in RF Plasma
- A New Method for Size Control of Ultrafine Particles and Effect of Electric Field
- 南西諸島の稀少哺乳類3種の分子系統学的位置付け
- Intra- and Interspecific Genetic Complexities of Two Eothenomys Species in Honshu, Japan(Animal Diversity and Evolution)
- Restriction Site Variation in Ribosomal DNA in 24 Species of the Order Galliformes
- Bipartition of Biconnected Graphs
- A karyological analysis of the Korean red-backed vole, Eothenomys regulus (Rodentia, Muridae), using differential staining methods
- Phylogenetic relationships of the short-faced mole, Scaptochirus moschatus (Mammalia : Eulipotyphla), among Eurasian fossorial moles, as inferred from mitochondrial and nuclear gene sequences
- An evolutionary view on the Japanese talpids based on nucleotide sequences
- Evolution and biogeography of talpid moles from continental East Asia and the Japanese islands inferred from mitochondrial and nuclear gene sequences.
- Evidence from nuclear DNA sequences sheds light on the phylogenetic relationships of pinnipedia: Single origin with affinity to musteloidea
- CORRELATION BETWEEN THE RADIATION EVENT OF WEASELS AND MARTENS (MUSTELIDAE; CARNIVORA) INFERRED FROM MULTIPLE NUCLEAR SEQUENCES(Taxonomy and Systematics,Abstracts of papers presented at the 75^ Annual Meeting of the Zoological Society of Japan)
- Molecular Phylogeny of Arctoids (Mammalia: Carnivora) with Emphasis on Phylogenetic and Taxonomic Positions of the Ferret-badgers and Skunks(Animal Diversity and Evolution)
- PHYLOGENETIC RELATIONSHIPS AMONG MUSTELIDS (MAMMALIA: CARNIVORA) INFERRED FROM MULTIPLE GENE SEQUENCES IN SINGLE OR COMBINED GENE ANALYSES(Taxonomy and Systematics & Cell Biology and Morphology,Abstracts of papers presented at the 74^ Annual Meeting o
- Phylogenetic Relationships and Divergence Times among Mustelids (Mammalia : Carnivora) Based on Nucleotide Sequences of the Nuclear Interphotoreceptor Retinoid Binding Protein and Mitochondrial Cytochrome b Genes(Animal Diversity and Evolution)
- Evolutionary trends of the mitochondrial lineage differentiation in species of genera Martes and Mustela
- Genetic relationships within and between the Japanese marten Martes melampus and the sable M. zibellina, based on variation of mitochondrial DNA and nuclear ribosomal DNA
- Rectriction Site Polymorphism in the Ribosomal DNA of Eight Species of Canidae and Mustelidae
- Seroepidemiological Survey of Lymphocytic Choriomeningitis Virus in Wild House Mice in China with Particular Reference to Their Subspecies
- 日本産野生ネズミ類の起源と地理的変異 (特集 生物地理学,分子生物学と出会う--生物地理学の新展開)
- LOCALIZATION OF lasp-2 IN CHICKEN PRIMARY CULTURED CELL(Cell Biology and Morphology,Abstracts of papers presented at the 76^ Annual Meeting of the Zoological Society of Japan)
- リーシュマニアのP-糖タンパク質遺伝子群 : Leishmania amazonensis の新しいP-糖タンパク質関連遺伝子のクローニング
- New Evidence That the tyr-157 and Tyr-159 Residues of Staphylococcal Exfoliative Toxin B Are Essential for its Toxicity
- Rapid Identification by Polymerase Chain Reaction of Staphylococcal Exfoliative Toxin Serotype A and B Genes
- An Extended INDO-CI Theory of the General Relation between Bond Length and Bond Order
- Theory of the Relation between Bond Length and Bond Order by an Extended INDO Method
- Measurements of Ionization Cross Sections of 4d-Electrons in Xenon by Electron Impact