Testing whether a subgraph is convex or isometric

Cabello, Sergio (avtor)

We consider the following two algorithmic problems: given a graph $G$ and a subgraph $H\subseteq G$, decide whether $H$ is an isometric or a geodesically convex subgraph of $G$. It is relatively easy to see that the problems can be solved by computing the distances between all pairs of vertices. We provide a conditional lower bound showing that, for sparse graphs with $n$ vertices and $\Theta(n)$ edges, we cannot expect to solve the problem in $O(n^{2-\varepsilon})$ time for any constant $\varepsilon>0$. We also show that the problem can be solved in subquadratic time for planar graphs and in near-linear time for graphs of bounded treewidth. Finally, we provide a near-linear time algorithm for the setting where $G$ is a plane graph and $H$ is defined by a few cycles in $G$.

• Jezik: Angleški jezik
• Ključne besede: convex subgraphs, isometric subgraphs, plane graphs
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.08 - Objavljeni znanstveni prispevek na konferenci
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2025
• Št. strani: Str. 12:1-12:16
• PID: 20.500.12556/RUL-176951
• UDK: 004.42:519.17
• DOI: 10.4230/LIPIcs.WADS.2025.12
• COBISS.SI-ID: 261640963
• Datum objave v RUL: 16.12.2025

Gradivo je del monografije

• Naslov: 19th International Symposium on Algorithms and Data Structures : WADS 2025, August 11–15, 2025, York University, Toronto, Canada
• Uredniki: Pat Morin, Eunjin Oh
• Kraj izida: Saarbrücken/Wadern
• Založnik: Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
• Leto izida: 2025
• ISBN: 978-3-95977-398-0
• COBISS.SI-ID: 261608451
• Naslov zbirke: Leibniz international proceedings in informatics
• Številčenje v zbirki: ǂvol. ǂ349
• ISSN zbirke: 1868-8969

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.