3 citations · 9 across the 10 of their papers we have counts for
5 papers · 1 filter
Cycle Decompositions and Constructive Characterizations
Irene Heinrich, Manuel Streicher
Decomposing an Eulerian graph into a minimum respectively maximum number of edge disjoint cycles is an NP-complete problem. We prove that an Eulerian graph decomposes into a unique…
Hajós' cycle conjecture for small graphs
Irene Heinrich, Marco V. Natale, Manuel Streicher
Hajós' conjecture states that an Eulerian graph of order n can be decomposed into at most (n-1)/2 edge-disjoint cycles. We describe preprocessing steps, heuristics and integer prog…
Cycle decompositions of pathwidth-6 graphs
Elke Fuchs, Laura Gellert, Irene Heinrich
Hajós conjecture asserts that a simple Eulerian graph on n vertices can be decomposed into at most (n - 1)/2 cycles. The conjecture is only proved for graph classes in which every…
Minimum Cycle Decomposition: A Constructive Characterization for Graphs of Treewidth Two with Node Degrees Two and Four
Irene Heinrich, Sven O. Krumke
Substantial efforts have been made to compute or estimate the minimum number of cycles needed to partition the edges of an Eulerian graph. We give an equivalent characteriza…
Counting Dominating Sets of Graphs
Irene Heinrich, Peter Tittmann
Counting dominating sets in a graph is closely related to the neighborhood complex of . We exploit this relation to prove that the number of dominating sets of a grap…