chordal bipartite graphs 1computational complexity 1convex bipartite graphs 1dynamic programming 1roman domination 1
From the 1 of 4 linked papers with an AI index.
Showing cs.DMShow all
2 papers · 1 filter
cs.DM2026
Maximum Edge Open Packing in Permutation, Interval, and Well-Partitioned Chordal Graphs
Gautam K. Das, Kamal Santra
Edge open packing is a relaxation of induced matching in which the selected edges may induce disjoint stars. We study the \textsc{Maximum Edge Open Packing} problem on permutation…
cs.DM2026
Roman-Type Domination on Convex and Chordal Bipartite Graphs: Algorithms and Hardness
Gautam K. Das, Kamal Santra
The paper investigates several Roman domination variants on convex and chordal bipartite graphs, providing polynomial‑time dynamic‑programming algorithms for convex bipartite graph…