Source author record

Haiko Müller

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics Computational Complexity math.CO

Catalog footprint

Research overview

3works

3topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Counting independent sets in strongly orderable graphs

We consider the problem of devising algorithms to count exactly the number of independent sets of a graph G . We show that there is a polynomial time algorithm for this problem when G is restricted to the class of strongly orderable graphs, a superclass of chordal bipartite graphs. We also show that such an algorithm exists for graphs of bounded clique-width. Our results extends to a more general setting of counting independent sets in a weighted graph and can be used to count the number of independent sets of any given size k .

preprint2015arXiv

Partitioning a Graph into Disjoint Cliques and a Triangle-free Graph

A graph $G = (V, E)$ is \emph{partitionable} if there exists a partition $\{A, B\}$ of $V$ such that $A$ induces a disjoint union of cliques and $B$ induces a triangle-free graph. In this paper we investigate the computational complexity of deciding whether a graph is partitionable. The problem is known to be $\NP$-complete on arbitrary graphs. Here it is proved that if a graph $G$ is bull-free, planar, perfect, $K_4$ -free or does not contain certain holes then deciding whether $G$ is partitionable is $\NP$-complete. This answers an open question posed by Thomass{é}, Trotignon and Vuškovi{ć}. In contrast a finite list of forbidden induced subgraphs is given for partitionable cographs.

preprint2014arXiv

NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph

This paper investigates the computational complexity of deciding whether the vertices of a graph can be partitioned into a disjoint union of cliques and a triangle-free subgraph. This problem is known to be $\NP$-complete on arbitrary graphs. We show that this problem remains $\NP$-complete even when restricted to planar graphs and perfect graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.