Edge-Reconstruction of Cartesian Product Graphs

Publikationen: Thesis / Studienabschlussarbeiten und HabilitationsschriftenDissertation

Standard

Edge-Reconstruction of Cartesian Product Graphs. / Wardynski, Marcin Jacek.
2020.

Publikationen: Thesis / Studienabschlussarbeiten und HabilitationsschriftenDissertation

Harvard

Wardynski, MJ 2020, 'Edge-Reconstruction of Cartesian Product Graphs', Dr.mont., Montanuniversität Leoben (000).

APA

Wardynski, M. J. (2020). Edge-Reconstruction of Cartesian Product Graphs. [Dissertation, Montanuniversität Leoben (000)].

Bibtex - Download

@phdthesis{71a554f181284353862f9a482dc9ead6,
title = "Edge-Reconstruction of Cartesian Product Graphs",
abstract = "This thesis solves the weak edge-reconstruction problem for Cartesian products. In other words, it is shown that any nontrivial finite or infinite Cartesian product G with edge-set E(G) is uniquely determined up to isomorphisms by any edge-deleted subgraph {G − e|e ∈ E(G)}. For finite Cartesian products the thesis also presents an algorithm for the computation of G from G − e in O(m∆²) time, where m is the size of G and ∆ its maximal degree. It improves the straightforward algorithm for reconstruction of G, which has complexity O(mn²), where n is the order of G. Because ∆ can be much smaller than n, the improvement can be substantial.",
keywords = "Edge-reconstruction, Cartesian product, graph algorithms, Kantenrekonstruktion, Kartesisches Produkt, Graph Algorithmen",
author = "Wardynski, {Marcin Jacek}",
note = "no embargo",
year = "2020",
language = "English",
school = "Montanuniversitaet Leoben (000)",

}

RIS (suitable for import to EndNote) - Download

TY - BOOK

T1 - Edge-Reconstruction of Cartesian Product Graphs

AU - Wardynski, Marcin Jacek

N1 - no embargo

PY - 2020

Y1 - 2020

N2 - This thesis solves the weak edge-reconstruction problem for Cartesian products. In other words, it is shown that any nontrivial finite or infinite Cartesian product G with edge-set E(G) is uniquely determined up to isomorphisms by any edge-deleted subgraph {G − e|e ∈ E(G)}. For finite Cartesian products the thesis also presents an algorithm for the computation of G from G − e in O(m∆²) time, where m is the size of G and ∆ its maximal degree. It improves the straightforward algorithm for reconstruction of G, which has complexity O(mn²), where n is the order of G. Because ∆ can be much smaller than n, the improvement can be substantial.

AB - This thesis solves the weak edge-reconstruction problem for Cartesian products. In other words, it is shown that any nontrivial finite or infinite Cartesian product G with edge-set E(G) is uniquely determined up to isomorphisms by any edge-deleted subgraph {G − e|e ∈ E(G)}. For finite Cartesian products the thesis also presents an algorithm for the computation of G from G − e in O(m∆²) time, where m is the size of G and ∆ its maximal degree. It improves the straightforward algorithm for reconstruction of G, which has complexity O(mn²), where n is the order of G. Because ∆ can be much smaller than n, the improvement can be substantial.

KW - Edge-reconstruction

KW - Cartesian product

KW - graph algorithms

KW - Kantenrekonstruktion

KW - Kartesisches Produkt

KW - Graph Algorithmen

M3 - Doctoral Thesis

ER -