Systematized Approaches to the Complexity of Subgraph Problems
スポンサーリンク
概要
- 論文の詳細を見る
This is a survey of issues related to the complexity of subgraph problems proved in a systematic way. It deals with vertex deletion and edge deletion problems that can be viewed as subgraph problems. General NP-completeness theorems for these problems are presented, as well as a systematized result that shows polynomial time algorithms for these problems restricted to series-parallel graphs. Another problem considered in this paper is the lexicographically first maximal subgraph problems that appear in connection with parallel complexity theory.
- 一般社団法人情報処理学会の論文
- 1991-02-10
著者
-
Miyano S
Human Genome Center Institute Of Medical Science The University Of Tokyo
-
Miyano Satoru
Research Institute Of Fundamental Information Science Faculty Of Science Kyushu University
関連論文
- Constructing biological pathway models with hybrid functional Petri nets
- Biopathways representation and simulation on hybrid functional Petri net
- Modeling and Simulation of Fission Yeast Cell Cycle on Hybrid Functional Petri Net(Hybrid Systems)(Concurrent Systems and Hybrid Systems)
- Knowledge Acquisition from Amino Sequences by Machine Learning System BONSAI
- XML documentation of biopathways and their simulations in Genomic Object Net
- Learning Theory Toward Genome Informatics
- A New Series of $\Delta^p_2$-Complete Problems
- Systematized Approaches to the Complexity of Subgraph Problems
- Parallel Algorithms for Refutation Tree Problem on Formal Graph Systems
- Using Maximal Independent Sets to Solve Problems in Parallel
- O(log^* n) Time Parallel Algorithm for Computing Bounded degree Maximal Subgraphs
- A Parallel Algorithm for the Maximal Co-Hitting Set Problem
- O(log^* n) Time Parallel Algorithm for Computing Bounded Degree Maximal Subgraphs
- Complexity of Finding Alphabet Indexing
- O(log^* n) Time Parallel Algorithm for Computing Bounded Degree Maximal Subgraphs