リケラボ論文検索は、全国の大学リポジトリにある学位論文・教授論文を一括検索できる論文検索サービスです。

リケラボ 全国の大学リポジトリにある学位論文・教授論文を一括検索するならリケラボ論文検索大学・研究所にある論文を検索できる

リケラボ 全国の大学リポジトリにある学位論文・教授論文を一括検索するならリケラボ論文検索大学・研究所にある論文を検索できる

大学・研究所にある論文を検索できる 「Linear-Time Recognition of Double-Threshold Graphs」の論文概要。リケラボ論文検索は、全国の大学リポジトリにある学位論文・教授論文を一括検索できる論文検索サービスです。
リケラボ

コピーが完了しました

URLをコピーしました

論文の公開元へ論文の公開元へ
書き出し

Linear-Time Recognition of Double-Threshold Graphs

Kobayashi, Yusuke Okamoto, Yoshio Otachi, Yota Uno, Yushi 京都大学 DOI:10.1007/s00453-021-00921-9

2022.04

概要

A graph G=(V, E) is a double-threshold graph if there exist a vertex-weight function w:V→ℝ and two real numbers lb, ub ∈ ℝ such that uv ∈ E if and only if lb ≤ w(u)+w(v) ≤ ub. In the literature, those graphs are studied also as the pairwise compatibility graphs that have stars as their underlying trees. We give a new characterization of double-threshold graphs that relates them to bipartite permutation graphs. Using the new characterization, we present a linear-time algorithm for recognizing double-threshold graphs. Prior to our work, the fastest known algorithm by Xiao and Nagamochi [Algorithmica 2020] ran in O(n³ m) time, where n and m are the numbers of vertices and edges, respectively.

論文の公開元へ

この論文で使われている画像

関連論文

関連論文をもっと見る

参考文献

1. Barrus, M.D.: Weakly threshold graphs. Discrete Math. Theor. Comput. Sci. (2018). https://doi.

org/10.23638/DMTCS-20-1-15 https://doi.org/10.23638/DMTCS-20-1-15 https://doi.org/10.23638/

DMTCS-20-1-15

2. Behr, R., Sivaraman, V., Zaslavsky, T.: Mock threshold graphs. Discret. Math. 341(8), 2159–2178

(2018). https://doi.org/10.1016/j.disc.2018.04.023

3. Benzaken, C., Hammer, P.L., de Werra, D.: Threshold characterization of graphs with Dilworth number

two. J. Graph Theory 9(2), 245–267 (1985). https://doi.org/10.1002/jgt.3190090207

4. Calamoneri, T., Sinaimeri, B.: Pairwise compatibility graphs: a survey. SIAM Rev. 58(3), 445–460

(2016). https://doi.org/10.1137/140978053

5. Gallai, T.: Transitiv orientierbare graphen. Acta Mathematica Academiae Scientiarum Hungaricae

18(1–2), 25–66 (1967). https://doi.org/10.1007/bf02020961

6. Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. North Holland, Amsterdam

(2004)

7. Hamburger, P., McConnell, R.M., Pór, A., Spinrad, J.P., Xu, Z.: Double threshold digraphs. In: MFCS

2018, volume 117 of LIPIcs, pp. 69:1–69:12 (2018). https://doi.org/10.4230/LIPIcs.MFCS.2018.69

8. Hammer, P.L., Mahadev, N.V.R.: Bithreshold graphs. SIAM J. Algebr. Discrete Methods 6(3), 497–506

(1985). https://doi.org/10.1137/0606049

9. Heggernes, P., van’t Hof, P., Meister, D., Villanger, Y.: Induced subgraph isomorphism on proper

interval and bipartite permutation graphs. Theor. Comput. Sci. 562, 252–269 (2015). https://doi.org/

10.1016/j.tcs.2014.10.002

10. Hell, P., Huang, J.: Interval bigraphs and circular arc graphs. J. Graph Theory 46(4), 313–327 (2004).

https://doi.org/10.1002/jgt.20006

11. Jamison, R.E., Sprague, A.P.: Double-threshold permutation graphs. J. Algebr. Combin. (2021). https://

doi.org/10.1007/s10801-021-01029-7

12. Jamison, R.E., Sprague, A.P.: Multithreshold graphs. J. Graph Theory 94(4), 518–530 (2020). https://

doi.org/10.1002/jgt.22541

13. Kearney, P.E., Munro, J.I., Phillips, D.: Efficient generation of uniform samples from phylogenetic

trees. In: WABI 2003, volume 2812 of Lecture Notes in Computer Science, pp. 177–189. Springer

(2003). https://doi.org/10.1007/978-3-540-39763-2_14

123

A Self-archived copy in

Kyoto University Research Information Repository

https://repository.kulib.kyoto-u.ac.jp

Algorithmica (2022) 84:1163–1181

1181

14. Ma, T.-H.: On the threshold dimension 2 graphs. Technical report, Institute of Information Science,

Nankang, Taipei, Taiwan (1993)

15. Mahadev, N.V.R., Peled, U.N.: Threshold Graphs and Related Topics. North Holland, Amsterdam

(1995)

16. McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discret. Math.

201(1–3), 189–241 (1999). https://doi.org/10.1016/S0012-365X(98)00319-7

17. Monma, C.L., Reed, B.A., Trotter, W.T.: Threshold tolerance graphs. J. Graph Theory 12(3), 343–362

(1988). https://doi.org/10.1002/jgt.3190120307

18. Puleo, G.J.: Some results on multithreshold graphs. Graphs Combin. 36(3), 913–919 (2020). https://

doi.org/10.1007/s00373-020-02168-7

19. Raschle, T., Simon, K.: Recognition of graphs with threshold dimension two. In STOC, pp. 650–661.

ACM (1995). https://doi.org/10.1145/225058.225283

20. Ravanmehr, V., Puleo, G.J., Bolouki, S., Milenkovic, O.: Paired threshold graphs. Discret. Appl. Math.

250, 291–308 (2018). https://doi.org/10.1016/j.dam.2018.05.008

21. Sen, M.K., Sanyal, B.K.: Indifference digraphs: a generalization of indifference graphs and semiorders.

SIAM J. Discrete Math. 7(2), 157–165 (1994). https://doi.org/10.1137/S0895480190177145

22. Spinrad, J.P., Brandstädt, A., Stewart, L.: Bipartite permutation graphs. Discrete Appl. Math. 18(3),

279–292 (1987). https://doi.org/10.1016/S0166-218X(87)80003-3

23. Sprague, A.P.: Recognition of bipartite permutation graphs. Congr. Numer. 112, 151–161 (1995)

24. Sterbini, A., Raschle, T.: An O(n 3 ) time algorithm for recognizing threshold dimension 2 graphs. Inf.

Process. Lett. 67(5), 255–259 (1998). https://doi.org/10.1016/S0020-0190(98)00112-4

25. West, D.B.: Short proofs for interval digraphs. Discrete Math. 178(1–3), 287–292 (1998). https://doi.

org/10.1016/S0012-365X(97)81840-7

26. Xiao, M., Nagamochi, H.: Characterizing star-PCGs. Algorithmica 82(10), 3066–3090 (2020). https://

doi.org/10.1007/s00453-020-00712-8

27. Yan, J.-H., Chen, J.-J., Gerard, J.C.: Quasi-threshold graphs. Discrete Appl. Math. 69(3), 247–255

(1996). https://doi.org/10.1016/0166-218X(96)00094-7

Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps

and institutional affiliations.

123

...

参考文献をもっと見る

全国の大学の
卒論・修論・学位論文
を
一発検索！

この論文の関連論文を見る