| Naslov: | Testing whether a subgraph is convex or isometric |
|---|
| Avtorji: | ID Cabello, Sergio (Avtor) |
|---|
| Datoteke: |  PDF - Predstavitvena datoteka, prenos (1,08 MB)
MD5: 5B29D4B9D018CA75239B5A81688741E9
 URL - Izvorni URL, za dostop obiščite https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.12
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.08 - Objavljeni znanstveni prispevek na konferenci |
|---|
| Organizacija: |  IMFM - Inštitut za matematiko, fiziko in mehaniko
|
|---|
| Povzetek: | 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$. |
|---|
| Ključne besede: | convex subgraphs, isometric subgraphs, plane graphs |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Leto izida: | 2025 |
|---|
| Št. strani: | Str. 12:1-12:16 |
|---|
| PID: | 20.500.12556/DiRROS-24738  |
|---|
| UDK: | 004.42:519.17 |
|---|
| DOI: | 10.4230/LIPIcs.WADS.2025.12 |
|---|
| COBISS.SI-ID: | 261640963 |
|---|
| Opomba: |
|
|---|
| Datum objave v DiRROS: | 16.12.2025 |
|---|
| Število ogledov: | 7 |
|---|
| Število prenosov: | 4 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
