DROPS

Document

Research

Generalized Fibonacci Cubes Based on Swap and Mismatch Distance

Authors: Marcella Anselmo, Giuseppa Castiglione, Manuela Flores, Dora Giammarresi, Maria Madonia, and Sabrina Mantaci

Published in: OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025)

Abstract

The hypercube of dimension n is the graph with 2ⁿ vertices associated to all binary words of length n and edges connecting pairs of vertices with Hamming distance equal to 1. Here, an edit distance based on swaps and mismatches is considered and referred to as tilde-distance. Accordingly, the tilde-hypercube is defined, with edges linking words having tilde-distance equal to 1. The focus is on the subgraphs of the tilde-hypercube obtained by removing all vertices having a given word as factor. If the word is 11, then the subgraph is called tilde-Fibonacci cube; in the case of a generic word, it is called generalized tilde-Fibonacci cube. The paper surveys recent results on the definition and characterization of those words that define generalized tilde-Fibonacci cubes that are isometric subgraphs of the tilde-hypercube. Finally, a special attention is given to the study of the tilde-Fibonacci cubes.

Cite as

Marcella Anselmo, Giuseppa Castiglione, Manuela Flores, Dora Giammarresi, Maria Madonia, and Sabrina Mantaci. Generalized Fibonacci Cubes Based on Swap and Mismatch Distance. In From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday. Open Access Series in Informatics (OASIcs), Volume 132, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{anselmo_et_al:OASIcs.Grossi.5,
  author =	{Anselmo, Marcella and Castiglione, Giuseppa and Flores, Manuela and Giammarresi, Dora and Madonia, Maria and Mantaci, Sabrina},
  title =	{{Generalized Fibonacci Cubes Based on Swap and Mismatch Distance}},
  booktitle =	{From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday},
  pages =	{5:1--5:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-391-1},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{132},
  editor =	{Conte, Alessio and Marino, Andrea and Rosone, Giovanna and Vitter, Jeffrey Scott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.5},
  URN =		{urn:nbn:de:0030-drops-238044},
  doi =		{10.4230/OASIcs.Grossi.5},
  annote =	{Keywords: Swap and mismatch distance, Isometric words, Hypercube}
}

Document

DOI: 10.4230/LIPIcs.CPM.2025.10

A Family of Partial Cubes with Minimal Fibonacci Dimension

Authors: Marcella Anselmo, Giuseppa Castiglione, Manuela Flores, Dora Giammarresi, Maria Madonia, and Sabrina Mantaci

Published in: LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)

Abstract

A partial cube G is a graph that admits an isometric embedding into some hypercube Q_k. This implies that vertices of G can be labeled with binary words of length k in a way that the distance between two vertices in the graph corresponds to the Hamming distance between their labels. The minimum k for which this embedding is possible is called the isometric dimension of G, denoted idim(G). A Fibonacci cube Γ_k is the partial cube obtained by deleting all the vertices in Q_k whose labels contain word 11 as factor. It turns out that any partial cube can be always isometrically embedded also in a Fibonacci cube Γ_d. The minimum d is called the Fibonacci dimension of G, denoted fdim(G). In general, idim(G) ≤ fdim(G) ≤ 2 ⋅ idim(G) -1. Despite there is a quadratic algorithm to compute the isometric dimension of a graph, the problem of checking, for a given G, whether idim(G) = fdim(G) is in general NP-complete. An important family of graphs for which this happens are the trees. We consider a kind of generalized Fibonacci cubes that were recently defined. They are the subgraphs of the hypercube Q_k that include only vertices that avoid words in a given set S and are referred to as Q_k(S). We prove some conditions on the words in S to obtain a family of partial cubes with minimal Fibonacci dimension equal to the isometric dimension.

Cite as

Marcella Anselmo, Giuseppa Castiglione, Manuela Flores, Dora Giammarresi, Maria Madonia, and Sabrina Mantaci. A Family of Partial Cubes with Minimal Fibonacci Dimension. In 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 331, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{anselmo_et_al:LIPIcs.CPM.2025.10,
  author =	{Anselmo, Marcella and Castiglione, Giuseppa and Flores, Manuela and Giammarresi, Dora and Madonia, Maria and Mantaci, Sabrina},
  title =	{{A Family of Partial Cubes with Minimal Fibonacci Dimension}},
  booktitle =	{36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-369-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{331},
  editor =	{Bonizzoni, Paola and M\"{a}kinen, Veli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.10},
  URN =		{urn:nbn:de:0030-drops-231044},
  doi =		{10.4230/LIPIcs.CPM.2025.10},
  annote =	{Keywords: Isometric sets of words, Hypercubes, Partial cubes, Isometric dimension, Generalized Fibonacci Cubes}
}

Search Results

Documents authored by Giammarresi, Dora

Generalized Fibonacci Cubes Based on Swap and Mismatch Distance

Abstract

Cite as

A Family of Partial Cubes with Minimal Fibonacci Dimension

Abstract

Cite as

Thanks for your feedback!

Could not send message