On Minimum Feedback Vertex Sets in Bipartite Graphs and Degree-Constraint Graphs

概要

論文の詳細を見る
We consider the minimum feedback vertex set problem for some bipartite graphs and degree-constrained graphs. We show that the problem is linear time solvable for bipartite permutation graphs and NP-hard for grid intersection graphs. We also show that the problem is solvable in O(n2log 6n) time for n-vertex graphs with maximum degree at most three.
The Institute of Electronics, Information and Communication Engineersの論文

著者

Takaoka Asahi
Department Of Communication And Integrated Systems Tokyo Institute Of Technology
Tayu Satoshi
Department Of Communication And Integrated Systems Tokyo Institute Of Technology
Ueno Shuichi
Department Of Biological Science Faculty Of Science Yamaguchi University
TAKAOKA Asahi
Department of Communications and Computer Engineering, Tokyo Institute of Technology

関連論文

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
Gene expression profiling of human myocardium with atrial fibrillation by DNA microarray analysis
Cardioprotective effects of angiotensin II receptor blockade on the molecular responses induced by mechanical stress in cardiac myocytes
DNA microarray analysis of the in vivo progression mechanism for heart failure in Dahl salt-sensitive rats
On the Complexity of Fault Testing for Reversible Circuits
A-1-26 On the Complexity of Fault Testing for Reversible Circuits
Analytical Device Model of SOI MOSFETs Including Self-Heating Effect
On Dynamic Fault Tolerance for WSI Networks
Orthogonal ray graphs and nano-PLA design (コンカレント工学)
Orthogonal ray graphs and nano-PLA design (回路とシステム)
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 (コンカレント工学)
On the Complexity of Three-Dimensional Orthogonal Face Routing
On the complexity of three-dimensional orthogonal face routing (回路とシステム)
On the Three-Dimensional Orthogonal Drawing of Series-Parallel Graphs
A-1-27 On the Three-Dimensional Layout of Butterfly Networks
A-1-31 A Note on Sparse Networks Tolerating Random Faults for Cycles(A-1. 回路とシステム, 基礎・境界)
On the Proper-Path-Decomposition of Trees
Fault-Tolerant Graphs for Hypercubes and Tori (Special Issue on Architectures, Algorithms and Networks for Massively parallel Computing)
Midblastula transition (MBT) of the cell cycles in the yolk and pigment granule-free translucent blastomeres obtained from centrifuged Xenopus embryos
ESTABLISHMENT A METHOD TO ANALYZE CELL CYCLE AND CELL DIFFERENTIATION UPON EARLY XENOPUS DEVELOPMENT USING TRANSPARENT BLASTOMERES(Developmental Biology,Abstracts of papers presented at the 75^ Annual Meeting of the Zoological Society of Japan)
CHANGES IN INTRACELLULAR CA^ CONCENTRATION DURING EARLY EMBRYONIC CELL CYCLES IN XENOPUS(Developmental Biology,Abstracts of papers presented at the 76^ Annual Meeting of the Zoological Society of Japan)
THE REGULATING MECHANISM OF CENTROSOME SEPARATION AFTER MID-BLASTULA TRANSITION (MBT) IN XENOPUS EMBRYOS(Developmental Biology,Abstracts of papers presented at the 76^ Annual Meeting of the Zoological Society of Japan)
FUNCTIONAL ANALYSIS OF PTEN AT GASTRULATION OF XENOPUS LAEVIS(Developmental Biology,Abstracts of papers presented at the 76^ Annual Meeting of the Zoological Society of Japan)
FUNCTIONAL ANALYSIS OF PTEN AT GASTRULATION OF XENOPUS LAEVIS(Developmental Biology,Abstracts of papers presented at the 75^ Annual Meeting of the Zoological Society of Japan)
On-Line Multicasting in All-Optical Networks
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
Expression of Matrix Metalloproteinases in Patients With Acute Myocardial Infarction
A Note on the Circuit-switched Fixed Routing in Networks (特集並列処理)
Fault-Tolerant Meshes with Efficient Layouts
AS-1-2 Lower Bounds for the Height of Three-Dimensional Channel Routing
On Two Problems of Nano-PLA Design
On the energy-aware mapping for NoCs (回路とシステム)
A-1-21 A Note on the Three-Dimensional Single-Active-Layer Routing
A-1-30 On the Three-Dimensional Single-Active-Layer Routing with Dual Channels
A-1-13 Universal Reversible Circuits
A-1-7 On the Complexity of Three-Dimensional Orthogonal Face Routing
On the Three-Dimensional Orthogonal Drawing of Outerplanar Graphs : Extended Abstract
On the Three-Dimensional Orthogonal Drawing of Outerplanar Graphs : Extended Abstract
On the Three-Dimensional Orthogonal Drawing of Outerplanar Graphs : Extended Abstract
On the three-dimensional single-active-layer routing (回路とシステム)
An Efficient Quantum Addition Circuit : Extended Abstract
An Efficient Quantum Addition Circuit : Extended Abstract
An Efficient Quantum Addition Circuit : Extended Abstract
On the three-dimensional single-active-layer routing (コンカレント工学)
A-1-32 A Note on Fault Testing for Reversible Circuits
Special Section on Discrete Mathematics and Its Applications
Efficient Embeddings of Binary Trees with Bounded Proper Pathwidth into Paths and Grids
The Complexity of Three-Dimensional Channel Routing
AS-1-3 Three-Dimensional Channel Routing is in NP
A-1-30 A Note on the Three-Dimensional Channel Routing(A-1. 回路とシステム, 基礎・境界)
The Complexity of Three-Dimensional Channel Routing
A-1-20 On the Quantum Query Complexity of All-Pairs Shortest Paths
The Complexity of Three-Dimensional Channel Routing
AS-1-4 On the Three-Dimensional Layout of Hypercubes
AS-1-1 The Complexity of Fault Testing for Reversible Circuits
A-7-1 A Note on Universally Ideal Secret-Sharing Schemes
A-1-14 A Note on the Maximum Balanced Biclique Problem
A-1-13 A Note on the Subtree Isomorphism Problem
MSA: mixed stochastic algorithm for placement with larger solution space (VLSI設計技術)
An Improved Simulated Annealing for 3D Packing with Sequence Triple and Quintuple Representations (ディペンダブルコンピューティング)
A-1-34 On the Complexity of Energy-Aware Mapping for NoCs
On Efficient Universal Quantum Circuits (回路とシステム)
On Efficient Universal Quantum Circuits (システム数理と応用)
On Efficient Universal Quantum Circuits
On Efficient Universal Quantum Circuits
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 (信号処理)
A-1-8 A Note on Two-Directional Orthogonal Ray Graphs
A-1-7 A Note on the Cutwidth of Trees
A-1-6 A Note on the Energy-Aware Mapping for NoCs
On the Complexity of Fault Testing for Reversible Circuits
A-1-9 The Complexity of the Densest κ-Subgraph Problem for Chordal Bipartite Graphs
A-1-10 Characterizations of Orthogonal Ray Trees
On Minimum Feedback Vertex Sets in Graphs
On Minimum Feedback Vertex Sets in Graphs
On Minimum Feedback Vertex Sets in Graphs
A Note on the Energy-Aware Mapping for NoCs
A Note on the Energy-Aware Mapping for NoCs
On Minimum Feedback Vertex Sets in Bipartite Graphs and Degree-Constraint Graphs
On Minimum Feedback Vertex Sets in Graphs (信号処理)
On Unit Grid Intersection Graphs
On Unit Grid Intersection Graphs
On Unit Grid Intersection Graphs
On Orthogonal Ray Trees (回路とシステム)
On Unit Grid Intersection Graphs
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
A-1-5 A Note on the Subtree Isomorphism Problem

On Minimum Feedback Vertex Sets in Bipartite Graphs and Degree-Constraint Graphs

スポンサーリンク

概要

著者

関連論文

スポンサーリンク