藤田 聡 FUJITA Satoshi

ID:9000046253910

広島大学 大学院工学研究科 情報工学専攻 Department of Information Engineering, Graduate School of Engineering Hiroshima University (2008年 CiNii収録論文より)

Search authors sharing the same name

Articles:  1-1 of 1

  • Maximum Connected Domatic Partition of Directed Path Graphs  [in Japanese]

    MITO Masaya , FUJITA Satoshi

    本稿では,グラフの最大連結支配集合分割問題について考察する.以下では,有向パスグラフの部分クラスに対してこの問題が多項式時間で解けることを示す.有向パスグラフとは,有向木上の有向パスによってモデル化される交差グラフであり,区間グラフのひとつの拡張になっている.本稿で考える有向パスグラフの部分クラスは,有向木中の入次数2以上のノードが高々ひとつであるという制約が課せられたクラスである.

    IPSJ SIG Notes 118, 25-32, 2008-05-20

    References (16)

Page Top