EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Minimum Monotone Spanning Trees

Emilio Di Giacomo, Walter Didimo, Eleni Katsanou, Lena Schlipf, Antonios Symvonis, Alexander Wolff

Algorithmica · 2027-02 · 89 (1)

DOI: 10.1007/s00453-026-01409-0 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algorithmica, online erschienen am 16.11.2026. Verfasst von Emilio Di Giacomo und 5 weiteren Autor:innen. Die Arbeit nennt 54 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Given a finite set S of points in the plane and a finite set $$\mathcal {D}$$ D of directions, a geometric spanning tree T of S is $$\mathcal {D}$$ D -monotone if every path in T is monotone with respect to some direction in $$\mathcal {D}$$ D . We study the problem of computing, for a given point set S and a given set $$\mathcal {D}$$ D of directions, a minimum-length $$\mathcal{D}$$ D -monotone spanning tree of S . We present a quadratic-time algorithm for two directions. More generally, we show that the problem belongs to the complexity class XP when parameterized by the number of directions. We further study, for a given positive integer k and point set S , the problem of finding a minimum-length $$\mathcal {D}$$ D -monotone spanning tree of S over all possible sets $$\mathcal {D}$$ D of k directions. We prove that this problem, too, is in XP when parameterized by k , and present two algorithms that run in $$O(n^2 \log n)$$ O ( n 2 log n ) and $$O(n^6)$$ O ( n 6 ) time for $$k=1$$ k = 1 and $$k=2$$ k = 2 , respectively, where n is the number of points in S . Finally, in contrast to the classical Euclidean minimum spanning tree of a set of points, whose vertex degree is bounded by six, we show that for every even integer k , there exists a point set $$S_k$$ S k and a set $$\mathcal {D}_k$$ D k of k directions such that any minimum-length $$\mathcal {D}_k$$ D k -monotone spanning tree of $$S_k$$ S k has maximum vertex degree 2 k .

Zitieren

APA

Giacomo, E. D., Didimo, W., Katsanou, E., Schlipf, L., Symvonis, A., & Wolff, A. (2027). Minimum Monotone Spanning Trees. Algorithmica, 89(1). https://doi.org/10.1007/s00453-026-01409-0

Vancouver

Giacomo ED, Didimo W, Katsanou E, Schlipf L, Symvonis A, Wolff A. Minimum Monotone Spanning Trees. Algorithmica. 2027;89(1). doi:10.1007/s00453-026-01409-0

BibTeX
@article{Giacomo2027,
  author = {Giacomo, Emilio Di and Didimo, Walter and Katsanou, Eleni and Schlipf, Lena and Symvonis, Antonios and Wolff, Alexander},
  title = {Minimum Monotone Spanning Trees},
  journal = {Algorithmica},
  year = {2027},
  volume = {89},
  number = {1},
  doi = {10.1007/s00453-026-01409-0}
}
Kostenlos starten →