dc.contributor.author | Ahn, Jungho | |
dc.contributor.author | Jaffke, Lars | |
dc.contributor.author | Kwon, O-Joung | |
dc.contributor.author | Lima, Paloma Thome de | |
dc.date.accessioned | 2021-10-04T07:54:29Z | |
dc.date.available | 2021-10-04T07:54:29Z | |
dc.date.created | 2021-10-01T13:22:48Z | |
dc.date.issued | 2021 | |
dc.identifier.issn | 0302-9743 | |
dc.identifier.uri | https://hdl.handle.net/11250/2787349 | |
dc.description.abstract | In this work, we solve three problems on well-partitioned chordal graphs. First, we show that every connected (resp., 2-connected) well-partitioned chordal graph has a vertex that intersects all longest paths (resp., longest cycles). It is an open problem [Balister et al., Comb. Probab. Comput. 2004] whether the same holds for chordal graphs. Similarly, we show that every connected well-partitioned chordal graph admits a (polynomial-time constructible) tree 3-spanner, while the complexity status of the Tree 3-Spanner problem remains open on chordal graphs [Brandstädt et al., Theor. Comput. Sci. 2004]. Finally, we show that the problem of finding a minimum-size geodetic set is polynomial-time solvable on well-partitioned chordal graphs. This is the first example of a problem that is NP -hard on chordal graphs and polynomial-time solvable on well-partitioned chordal graphs. Altogether, these results reinforce the significance of this recently defined graph class as a tool to tackle problems that are hard or unsolved on chordal graphs. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Springer | en_US |
dc.title | Three problems on well-partitioned chordal graphs | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | acceptedVersion | en_US |
dc.rights.holder | Copyright Springer Nature Switzerland AG 2021 | en_US |
cristin.ispublished | true | |
cristin.fulltext | postprint | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.1007/978-3-030-75242-2_2 | |
dc.identifier.cristin | 1942211 | |
dc.source.journal | Lecture Notes in Computer Science (LNCS) | en_US |
dc.source.pagenumber | 23-36 | en_US |
dc.identifier.citation | Lecture Notes in Computer Science (LNCS). 2021, 12701, 23-36. | en_US |
dc.source.volume | 12701 | en_US |