-
Article
Open AccessScience with a Small Two-Band UV-Photometry Mission II: Observations of Stars and Stellar Systems
We outline the impact of a small two-band UV-photometry satellite mission on the field of stellar physics, magnetospheres of stars, binaries, stellar clusters, interstellar matter, and exoplanets. On specific ...
-
Article
The Complexity of Equality Constraint Languages
We classify the computational complexity of all constraint satisfaction problems where the constraint language is preserved by all permutations of the domain. A constraint language is preserved by all permuta...
-
Chapter and Conference Paper
Clustered Planarity: Small Clusters in Eulerian Graphs
We present several polynomial-time algorithms for c-planarity testing for clustered graphs with clusters of size at most three. The most general result concerns a special class of Eulerian graphs, namely graph...
-
Chapter and Conference Paper
Maximal Infinite-Valued Constraint Languages
We systematically investigate the computational complexity of constraint satisfaction problems for constraint languages over an infinite domain. In particular, we study a generalization of the wellestablished ...
-
Article
Free binary decision diagrams for the computation of EAR n
Free binary decision diagrams (FBDDs) are graph-based data structures representing Boolean functions with the constraint (additional to binary decision diagram) that each variable is tested at most once during...
-
Chapter and Conference Paper
Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs
We present a fixed parameter tractable algorithm for the Independent Set problem in 2-dir graphs and also its generalization to d -dir graphs. A graph belongs to the class of d ...
-
Chapter and Conference Paper
The Complexity of Equality Constraint Languages
We apply the algebraic approach to infinite-valued constraint satisfaction to classify the computational complexity of all constraint satisfaction problems with templates that have a highly transitive automorp...
-
Article
On the Chromatic Number of the Visibility Graph of a Set of Points in the Plane
The visibility graph V(P) of a point set P \subseteq R2 has vertex set P, such that two points v,w ∈ P are adjacent whenever there is no other point in P on the line segment between v and w. We study the chromati...
-
Chapter and Conference Paper
On the Complexity of the Balanced Vertex Ordering Problem
We consider the problem of finding a balanced ordering of the vertices of a graph. More precisely, we want to minimise the sum, taken over all vertices v, of the difference between the number of neighbours to the...
-
Chapter and Conference Paper
An Algorithm for Cyclic Edge Connectivity of Cubic Graphs
The cyclic edge connectivity is the size of a smallest edge cut in a graph such that at least two of the connected components contain cycles. We present an algorithm running in time O(n 2l...
-
Chapter and Conference Paper
Noncrossing Hamiltonian Paths in Geometric Graphs
A geometric graph is a graph embedded in the plane in such a way that vertices correspond to points in general position and edges correspond to segments connecting the appropriate points. A noncrossing Hamilto...
-
Chapter and Conference Paper
Optimal Free Binary Decision Diagrams for Computation of EARn
Free binary decision diagrams (FBDDs) are graph-based data structures representing Boolean functions with a constraint (additional to binary decision diagrams) that each variable is tested during the computati...
-
Chapter and Conference Paper
Complexity of Pattern Coloring of Cycle Systems
A k-cycle system is a system of cyclically ordered k-tuples of a finite set. A pattern is a sequence of letters. A coloring of a k-cycle system with respect to a set of patterns of length k is proper iff each cyc...
