演講後的研究討論

之前，曾到國立台北商業技術學院演講。演講中，我提出一個O(n^2)的演算法，在Chordal bipartite graphs 上解決兩個 Total domination的變形問題: Signed total domination 和Minus total domination。 幾天過後，開始有學生或者研究的同好，想要在Chordal bipartite graphs 的Subclasses 上解決這兩類的問題，例如: Bipartite permutation graphs, Biconvex bipartite graphs, 或者是 Convex bipartite graphs。其實，我在演講上所提出的結果，已發表在去年的Information Processing Letters期刊。所以今年二月初，我早已想出統整的線性時間演算法，在Biconvex bipartite graphs上解決Signed total domination 和Minus total domination。同時，將此結果投到一個國際期刊，目前正在審查中。由於 Bipartite permutation graphs 是 Biconvex bipartite graphs的Subclass，因此也可在線性時間內解決這兩個問題。正因為如此，我只好請他們將焦點放在Convex bipartite graph上囉！至於我呢？我打算在暑假的時候忙另一個研究的問題。到目前為止，進度還不錯。希望暑假結束前能有一個小結果產生。