Metraipolis › archive › dc_4ce50259a778
Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs — arXiv:2610.02275
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.02275
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-06T08:25:39.933Z
- SHA-256 of the archived text
2d56f578f19df899cb2d42d882e7c0ad4938148324d6895501a785e1f9db6876- Stable URL of this page
https://metraipolis.com/documento/dc_4ce50259a778
How to cite
Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs — arXiv:2610.02275 — arXiv (en), https://arxiv.org/abs/2610.02275 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4ce50259a778 (Metraipolis archive dc_4ce50259a778, sha256 2d56f578f19df899cb2d42d882e7c0ad4938148324d6895501a785e1f9db6876)
BibTeX
@misc{dc4ce50259a778,
title = {Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs — arXiv:2610.02275},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.02275},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4ce50259a778; sha256 2d56f578f19df899cb2d42d882e7c0ad4938148324d6895501a785e1f9db6876},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.02275. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
An edge open packing is a set of edges whose endpoints induce a disjoint union of stars. We study the problem of finding a maximum edge open packing in AT-free, chordal, and convex bipartite graphs. For AT-free graphs, we use the oriented star-conflict graph $A_G$, introduced by Das and Santra, for which $\rho_e^o(G)=\alpha(A_G)$, and prove that $A_G$ is AT-free whenever $G$ is AT-free. Consequently, a known maximum independent set algorithm for AT-free graphs yields an $O(n^2+m^4)$-time algorithm for Maximum Edge Open Packing, where $n$ and $m$ denote the numbers of vertices and edges of $G$, respectively. For chordal graphs, we develop an $O(n^4)$-time dynamic programming algorithm over a nice tree decomposition derived from a clique tree, exploiting the structural fact that the endpoint set of an edge open packing intersects every clique in at most two vertices. Finally, for convex bipartite graphs, we obtain an $O(n^4)$-time dynamic programming algorithm based on two boundary indices that separate consecutive star components. This result extends the previously known algorithm for biconvex bipartite graphs and, in particular, provides an improved explicit running-time bound for that class. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-05 in math.CO). Categorie arXiv: Discrete Mathematics (cs.DM) ; Combinatorics (math.CO). Pagina del lavoro: https://arxiv.org/abs/2610.02275 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-06T08:18:48.323Z dalla pagina https://arxiv.org/catchup/math.CO/2026-10-05?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).