Efficient Minus and Signed Domination in Proper Interval Graphs with a Totally Unimodular Structure
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).
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}
}
EUVIMED