Generalizing the decomposition of a connected planar graph into a tree and a dual tree, we prove a combinatorial analog of the classic Helmholtz–Hodge decomposition of a smooth vector field. ...Specifically, we show that for every polyhedral complex,
K
, and every dimension,
p
, there is a partition of the set of
p
-cells into a maximal
p
-tree, a maximal
p
-cotree, and a collection of
p
-cells whose cardinality is the
p
-th reduced Betti number of
K
. Given an ordering of the
p
-cells, this tri-partition is unique, and it can be computed by a matrix reduction algorithm that also constructs canonical bases of cycle and boundary groups.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OBVAL, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
In this paper, we modify a known parallel cograph-recognition algorithm proposed by Nikolopoulos and Palios S.D. Nikolopoulos, L. Palios, Efficient parallel recognition of cographs, Discrete Applied ...Mathematics 150 (1–3) (2005) 182–215 and provide a new analysis of the algorithm. Given an input graph
G
with
n
vertices and
m
edges, we obtain the following three results based on our analysis:
1.
When
G
is
k
-regular for a fixed positive integer
k
, the cograph-recognition problem can be optimally solved in
O
(
log
n
)
time using
O
(
n
+
m
log
n
)
processors on an EREW PRAM.
2.
When
G
is
k
-regular for
k
=
O
(
log
log
n
)
, the cograph-recognition problem can be solved in
O
(
log
n
log
log
n
)
time using
O
(
n
+
m
log
n
)
processors on an EREW PRAM.
3.
Given a positive integer
α
=
O
(
log
log
n
)
, the cograph-recognition problem can be solved in
O
(
log
n
log
log
n
)
time using
O
(
n
+
m
log
n
)
processors on an EREW PRAM, provided the number of vertices in
G
with degree larger than
α
is at most
O
(
log
n
)
.
The above results improve upon the previously best known result, which took
O
(
log
2
n
)
time using
O
(
n
+
m
log
n
)
processors on an EREW PRAM.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Adding an Edge in a Cograph Nikolopoulos, Stavros D.; Palios, Leonidas
Graph-Theoretic Concepts in Computer Science,
2005
Book Chapter, Conference Proceeding
Peer reviewed
In this paper, we establish structural properties of cographs which enable us to present an algorithm which, for a cograph G and a non-edge xy (i.e., two non-adjacent vertices x and y) of G, finds ...the minimum number of edges that need to be added to the edge set of G such that the resulting graph is a cograph and contains the edge xy. The motivation for this problem comes from algorithms for the dynamic recognition and online maintenance of graphs; the proposed algorithm could be a suitable addition to the algorithm of Shamir and Sharan 13 for the online maintenance of cographs. The proposed algorithm runs in time linear in the size of the input graph and requires linear space.
Full text
Available for:
FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NUK, OBVAL, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
Software watermarking involves embedding a unique identifier, i.e., a watermark value, within a software to discourage software theft; to this end, several graph theoretic watermark methods encode ...the watermark values as graph structures and embed them in application programs using a wide range of algorithmic techniques. In this paper we propose an efficient method for encoding the same watermark value into several different graphs, we call it multiple encoding, answering thus the question we have recently left open. In particular, we propose an efficient algorithm which embed a cograph Gπ* into a reducible permutation graph Fπ* by first computing the cotree of Gπ* then computing a rooted binary tree having specific node-value and child-parent properties, and finally, based on these properties, producing a reducible permutation graph Fπ*. In light of our recent encoding algorithms which encode a watermark value w as a self-inverting permutation π* and the permutation π* into several cographs G1π*, G2π*,...,Gnπ*, we conclude that we can efficiently encode the same watermark value w into several reducible permutation graphs F1π*, F2π*,..., Fnπ*, n ≥ 2. This property causes a codec watermarking system resilient to attacks since we can embed multiple copies of the same watermark value w into an application program. We also propose decoding algorithms which efficiently extract the watermark value w from the reducible permutation graph Fπ*.
In a software watermarking environment, several graph theoretic watermark methods encode the watermark values as graph structures and embed them in application programs. In this paper we extended the ...class of graphs which can be efficiently used in a software watermarking system by proposing an efficient codec system, i.e., encoding and decoding algorithms that embed/extract watermark values into/from cographs through the use of self-inverting permutations. More precisely, we present a codec system which takes as input an integer ω as watermark value, converts it into a self-inverting permutation π*, and then encodes the permutation π* as a cograph. The main property of our codec system is its ability to encode the same integer ω, using a self-inverting permutation π*, into more than one cograph. This property causes our system to be resilient to attacks since it can embed multiple copies of the same watermark number ω into an application program. Moreover, the proposed codec system has low time complexity and can be easily implemented.
By introducing collision information into divide-and-conquer distinguishers, the existing collision-optimized side-channel attacks transform the given candidate space into a significantly smaller ...collision space, thus achieving more efficient key recovery. However, the candidates of the first several sub-keys shared by collision chains are still repeatedly detected, which happens very frequently and brings huge computational overhead. To alleviate this, we propose a highly-efficient collision-optimized attack named Collision Tree (CoTree). This collision detection tool exploits tree structure to store the chains created from the same sub-chain on the same branch, thus significantly reducing the storage requirements. It then benefits from the properties of both tree and collisions, and exploits a top-down tree building procedure and traverses each node only once when detecting their collisions with a candidate of the sub-key currently under consideration. Finally, unlike the traditional top-down node removal, CoTree launches a bottom-up branch removal procedure to remove the chains unsatisfying the collision conditions from the tree after traversing all the considered candidates of this sub-key, thus avoiding the traversal of the branches satisfying the collision condition. These strategies make our CoTree significantly alleviate the repetitive collision detection, and our experiments verify that it significantly outperforms the existing works.
The volume integral equation method based on the current vector potential approximated by means edge element basis function is a well-established approach for 3-D eddy currents computation. The ...application of the method is straightforward when simply connected geometries and no connection with external circuits are involved. In this case, in fact, the solving system is easily obtained based on tree-cotree decomposition of the primal graph. However, when multiply connected geometries or external generators are considered, "additional" degrees of freedom, not related to interior cotree edges of the primal graph, need to be identified and involved to assure the consistency of the numerical solution. In this article, the link between the volume integral equation method and the circuit is investigated in detail, and the circuit view is used as a guide for systematically finding the additional degrees of freedom arising in case of multiply connected geometries and/or external circuits. In particular, the dual graph is introduced as the support of the circuit and it is shown that this is the natural frame for taking the topology into account. For multiply connected geometries, the additional degrees of freedom are related to loop currents crossing one only time (or an odd number of times) any cutting surface making the domain simply connected, and are found by applying a minimum path algorithm on the dual graph forming the circuit. In case of conducting domain connected to an external generator, an extended dual graph is introduced for finding the further additional degrees of freedom. This article also researches into the possibility to replace the usual current density of the elements, obtained via facet-element shape functions and exactly matching the current of the faces, with a uniform current density obtained by means of a minimum error procedure and approximately matching the current of the faces. The use of this uniform current density, besides improving the calculation time and the accuracy of the coupling coefficients, also allows the extension of the volume integral equation method to discretizations of the problem domain made of arbitrarily shaped polyhedral elements.
A method classically used in the lower polynomial degree for the construction of a finite element basis of the space of divergence-free functions is here extended to any polynomial degree for a ...bounded domain without topological restrictions. The method uses graphs associated with two differential operators: the gradient and the divergence, and selects the basis using a spanning tree of the first graph. It can be applied for the two main families of degrees of freedom, weights and moments, used to express finite element differential forms.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Combining the traditional mymargin mortar-element mymargin method (MEM) and the tree-cotree technique, we present a mixed MEM (MMEM) based on a hybrid mesh to solve 3-D Maxwell's eigenvalue problems ...with the absorbing boundary condition (ABC). In this MMEM, to couple the different discretizations in hexahedral and tetrahedral subdomains, we design a mortar condition by which the degrees of freedom (DOFs) associated with the interface of hexahedral subdomains can be eliminated. When implementing the tree-cotree technique, the electric field and the test function are expressed by the lowest-order vector basis functions (edge elements) and the gradient of the first-order scalar nodal basis functions, which leads to a singular submatrix <inline-formula> <tex-math notation="LaTeX">\bar {\bar {E}}_{\mathrm {sub}} </tex-math></inline-formula> in the mortar condition. Therefore, in this work, we introduce a method for selecting tree edges and cotree edges of hexahedral meshes to make <inline-formula> <tex-math notation="LaTeX">\bar {\bar {E}}_{\mathrm {sub}} </tex-math></inline-formula> nonsingular. Numerical experiments show that the MMEM can not only remove dc spurious modes but also retain physical modes. The numerical results of the MMEM are consistent with those of the commercial software COMSOL.
Power cables have complex geometries in order to reduce their ac resistance. Although there are many different cable designs, most have in common that their inner conductors' cross section is divided ...into several electrically insulated conductors, which are twisted over the cable's length (helicoidal symmetry). In previous works, we presented how to exploit this symmetry by means of dimensional reduction within the <inline-formula> <tex-math notation="LaTeX">\mathrm {H}-\varphi </tex-math></inline-formula> formulation of the eddy current problem. Here, the dimensional reduction is based on a coordinate transformation from the Cartesian coordinate system to a helicoidal coordinate system. This contribution focuses on how this approach can be incorporated into the magnetic vector potential-based <inline-formula> <tex-math notation="LaTeX">\mathrm {A}-v </tex-math></inline-formula> formulation.
PDF
