A note on the computational complexity of hierarchical overlapping clustering

Mirko Křivánek

Displaying similar documents to “A note on the computational complexity of hierarchical overlapping clustering”

Extremal problems for forbidden pairs that imply hamiltonicity

Ralph Faudree, András Gyárfás (1999)

Discussiones Mathematicae Graph Theory

Similarity:

Let C denote the claw $K_{1, 3}$ , N the net (a graph obtained from a K₃ by attaching a disjoint edge to each vertex of the K₃), W the wounded (a graph obtained from a K₃ by attaching an edge to one vertex and a disjoint path P₃ to a second vertex), and $Z_{i}$ the graph consisting of a K₃ with a path of length i attached to one vertex. For k a fixed positive integer and n a sufficiently large integer, the minimal number of edges and the smallest clique in a k-connected graph G of order n that is CY-free...

The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs

Ladislav Nebeský (2006)

Czechoslovak Mathematical Journal

Similarity:

If $G$ is a connected graph of order $n \geq 1$ , then by a hamiltonian coloring of $G$ we mean a mapping $c$ of $V (G)$ into the set of all positive integers such that $| c (x) - c (y) | \geq n - 1 - D_{G} (x, y)$ (where $D_{G} (x, y)$ denotes the length of a longest $x - y$ path in $G$ ) for all distinct $x, y \in V (G)$ . Let $G$ be a connected graph. By the hamiltonian chromatic number of $G$ we mean $min (max (c (z); z \in V (G))),$ where the minimum is taken over all hamiltonian colorings $c$ of $G$ . The main result of this paper can be formulated as follows: Let $G$ be a connected graph of order $n \geq 3$ . Assume that there exists...

Differential approximation of NP-hard problems with equal size feasible solutions

Jérôme Monnot (2002)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem $π$ which only differ on a linear transformation of their objective functions. This...

Measures of traceability in graphs

Varaporn Saenpholphat, Futaba Okamoto, Ping Zhang (2006)

Mathematica Bohemica

Similarity:

For a connected graph $G$ of order $n \geq 3$ and an ordering $s v_{1}$ , $v_{2}, \dots, v_{n}$ of the vertices of $G$ , $d (s) = \sum_{i = 1}^{n - 1} d (v_{i}, v_{i + 1})$ , where $d (v_{i}, v_{i + 1})$ is the distance between $v_{i}$ and $v_{i + 1}$ . The traceable number $t (G)$ of $G$ is defined by $t (G) = min \}d (s)\{,$ where the minimum is taken over all sequences $s$ of the elements of $V (G)$ . It is shown that if $G$ is a nontrivial connected graph of order $n$ such that $l$ is the length of a longest path in $G$ and $p$ is the maximum size of a spanning linear forest in $G$ , then $2 n - 2 - p \leq t (G) \leq 2 n - 2 - l$ and both these bounds are sharp. We establish a formula for the traceable...

Proof of an intersection theorem via graph homomorphisms.

Dinur, Irit, Friedgut, Ehud (2006)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Hamiltonian colorings of graphs with long cycles

Ladislav Nebeský (2003)

Mathematica Bohemica

Similarity:

By a hamiltonian coloring of a connected graph $G$ of order $n \geq 1$ we mean a mapping $c$ of $V (G)$ into the set of all positive integers such that $| c (x) - c (y) | \geq n - 1 - D_{G} (x, y)$ (where $D_{G} (x, y)$ denotes the length of a longest $x - y$ path in $G$ ) for all distinct $x, y \in G$ . In this paper we study hamiltonian colorings of non-hamiltonian connected graphs with long cycles, mainly of connected graphs of order $n \geq 5$ with circumference $n - 2$ .