Enumeration of Minimal Tropical Connected Sets

Ivan Bliznets; Danil Sagunov; Eugene Tagin

doi:10.1007/978-3-031-30448-4_10

Enumeration of Minimal Tropical Connected Sets

Ivan Bliznets, Danil Sagunov, Eugene Tagin

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

A subset of vertices in a vertex-colored graph is called tropical if R subset. This paper is dedicated to the enumeration of all minimal tropical connected sets in various classes of graphs. We show that all minimal tropical connected sets can be enumerated in time on n-vertex interval graph which improves previous upper bound obtained by Kratsch et al. Moreover, for chordal and general class of graphs we present algorithms with running times in respectively. The last two algorithms answer question implicitly asked in the paper [Kratsch et al.

Original language	English
Title of host publication	Algorithms and Complexity - 13th International Conference, CIAC 2023, Proceedings
Editors	Marios Mavronicolas
Pages	127-141
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-031-30448-4_10
Publication status	Published - 25 Apr 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13898 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Bibliographical note

Funding Information:
Work of Ivan Bliznets is supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No 853234).

Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Keywords

tropical sets
enumeration algorithms
graph motif
chordal graphs
beating brute-force

Access to Document

10.1007/978-3-031-30448-4_10

978-3-031-30448-4_10Final published version, 449 KBLicence: Taverne

Cite this

Bliznets, I., Sagunov, D., & Tagin, E. (2023). Enumeration of Minimal Tropical Connected Sets. In M. Mavronicolas (Ed.), Algorithms and Complexity - 13th International Conference, CIAC 2023, Proceedings (pp. 127-141). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13898 LNCS). https://doi.org/10.1007/978-3-031-30448-4_10

@inproceedings{2fb36cab008b476d8e6ce117014c15a0,

title = "Enumeration of Minimal Tropical Connected Sets",

abstract = "A subset of vertices in a vertex-colored graph is called tropical if R subset. This paper is dedicated to the enumeration of all minimal tropical connected sets in various classes of graphs. We show that all minimal tropical connected sets can be enumerated in time on n-vertex interval graph which improves previous upper bound obtained by Kratsch et al. Moreover, for chordal and general class of graphs we present algorithms with running times in respectively. The last two algorithms answer question implicitly asked in the paper [Kratsch et al.",

keywords = "tropical sets, enumeration algorithms, graph motif, chordal graphs, beating brute-force",

author = "Ivan Bliznets and Danil Sagunov and Eugene Tagin",

note = "Funding Information: Work of Ivan Bliznets is supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation program (grant agreement No 853234). Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.",

year = "2023",

month = apr,

day = "25",

doi = "10.1007/978-3-031-30448-4_10",

language = "English",

isbn = "9783031304477",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "127--141",

editor = "Marios Mavronicolas",

booktitle = "Algorithms and Complexity - 13th International Conference, CIAC 2023, Proceedings",

}

Bliznets, I, Sagunov, D & Tagin, E 2023, Enumeration of Minimal Tropical Connected Sets. in M Mavronicolas (ed.), Algorithms and Complexity - 13th International Conference, CIAC 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13898 LNCS, pp. 127-141. https://doi.org/10.1007/978-3-031-30448-4_10

Enumeration of Minimal Tropical Connected Sets. / Bliznets, Ivan; Sagunov, Danil; Tagin, Eugene.
Algorithms and Complexity - 13th International Conference, CIAC 2023, Proceedings. ed. / Marios Mavronicolas. 2023. p. 127-141 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13898 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Enumeration of Minimal Tropical Connected Sets

AU - Bliznets, Ivan

AU - Sagunov, Danil

AU - Tagin, Eugene

N1 - Funding Information: Work of Ivan Bliznets is supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No 853234). Publisher Copyright: © 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

PY - 2023/4/25

Y1 - 2023/4/25

N2 - A subset of vertices in a vertex-colored graph is called tropical if R subset. This paper is dedicated to the enumeration of all minimal tropical connected sets in various classes of graphs. We show that all minimal tropical connected sets can be enumerated in time on n-vertex interval graph which improves previous upper bound obtained by Kratsch et al. Moreover, for chordal and general class of graphs we present algorithms with running times in respectively. The last two algorithms answer question implicitly asked in the paper [Kratsch et al.

AB - A subset of vertices in a vertex-colored graph is called tropical if R subset. This paper is dedicated to the enumeration of all minimal tropical connected sets in various classes of graphs. We show that all minimal tropical connected sets can be enumerated in time on n-vertex interval graph which improves previous upper bound obtained by Kratsch et al. Moreover, for chordal and general class of graphs we present algorithms with running times in respectively. The last two algorithms answer question implicitly asked in the paper [Kratsch et al.

KW - tropical sets

KW - enumeration algorithms

KW - graph motif

KW - chordal graphs

KW - beating brute-force

UR - http://www.scopus.com/inward/record.url?scp=85161422523&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-30448-4_10

DO - 10.1007/978-3-031-30448-4_10

M3 - Conference contribution

SN - 9783031304477

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 127

EP - 141

BT - Algorithms and Complexity - 13th International Conference, CIAC 2023, Proceedings

A2 - Mavronicolas, Marios

ER -

Bliznets I, Sagunov D, Tagin E. Enumeration of Minimal Tropical Connected Sets. In Mavronicolas M, editor, Algorithms and Complexity - 13th International Conference, CIAC 2023, Proceedings. 2023. p. 127-141. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-30448-4_10