EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Efficient Minus and Signed Domination in Proper Interval Graphs with a Totally Unimodular Structure

Chuan-Min Lee

Axioms · 05.03.2026 · 15 (3) · 191

DOI: 10.3390/axioms15030191 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Axioms, online erschienen am 05.03.2026. Verfasst von Chuan-Min Lee. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 17 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The efficient minus domination problem (EMDP) and the efficient signed domination problem (ESDP) are domination-type problems in graphs. These problems are known to be NP-complete on chordal graphs and polynomially solvable on chain interval graphs, while the complexity on proper interval graphs remained open. By exploiting the totally unimodular structure of the closed-neighborhood matrix induced by a proper interval ordering, we obtain linear programming formulations under which both the EMDP and ESDP become polynomially solvable. The same perspective naturally extends to vertex-weighted settings and to other domination variants defined by similar neighborhood constraints.

Zitieren

APA

Lee, C. (2026). Efficient Minus and Signed Domination in Proper Interval Graphs with a Totally Unimodular Structure. Axioms, 15(3), 191. https://doi.org/10.3390/axioms15030191

Vancouver

Lee C. Efficient Minus and Signed Domination in Proper Interval Graphs with a Totally Unimodular Structure. Axioms. 2026;15(3):191. doi:10.3390/axioms15030191

BibTeX
@article{Lee2026,
  author = {Lee, Chuan-Min},
  title = {Efficient Minus and Signed Domination in Proper Interval Graphs with a Totally Unimodular Structure},
  journal = {Axioms},
  year = {2026},
  volume = {15},
  number = {3},
  pages = {191},
  doi = {10.3390/axioms15030191}
}
Kostenlos starten →