A Representation Diagram for Maximal Independent Sets of a Graph(Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• Let H=(V(H), E(H))be a directed graph with distinguished vertices s and t. An st-path in H is a simple directed path starting from s and ending at t. Let P(H)be defined as{S|S is the set of vertices on an st-path in H(s and t are excluded)}. For an undirected graph G=(V(G), E(G))with V(G)⫅V(H)-{s, t}, if the family on maximal independent sets of G coincides with P(H), we call H an MIS-diagram for G. In this paper, we provide a necessary and sufficient condition for a directed gradph to be an MIS-diagram for an undirected graph. We also show that an undirected graph G has an MIS-diagram iff G is a cocomparability graph. Based on the proof of the latter result, we can construct an efficient algorithm for generating all maximal independent sets of a cocomparability graph.

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

著者

• Kashiwabara Toshinobu

  The Graduate School Of Information Science And Technology Osaka University

• Kashiwabara Toshinobu

  The Department Of Information And Computer Sciences Osaka University

• Masuda S

  Kobe Univ. Kobe Jpn

• Masuda Sumio

  The Department Of Electrical And Electronics Engineering Kobe University

• TAKI Masakuni

  the Department of Information Engineering, Nara National College of Technology

• Taki Masakuni

  The Department Of Information Engineering Nara National College Of Technology

関連論文

• Expressive Power of Quantum Pushdown Automata with Classical Stack Operations under the Perfect-Soundness Condition(Computation and Computational Models)
• On the Power of Non-deterministic Quantum Finite Automata(Special Issue on Selected Papers from LA Symposium)
• An Exponential Lower Bound on the Size of a Binary Moment Diagram Representing Integer Division (Special Section on Discrete Mathematics and Its Applications)
• A Representation Diagram for Maximal Independent Sets of a Graph(Special Section on Discrete Mathematics and Its Applications)
• An A^* Algorithm with a New Heuristic Distance Function for the 2-Terminal Shortest Path Problem (Algorithms and Data Structures)

スポンサーリンク