The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
A K3-WORM coloring of a graph G is an assignment of colors to the vertices in such a way that the vertices of each K3-subgraph of G get precisely two colors. We study graphs G which admit at least one such coloring. We disprove a conjecture of Goddard et al. [Congr. Numer. 219 (2014) 161-173] by proving that for every integer k ≥ 3 there exists a K3-WORM-colorable graph in which the minimum number of colors is exactly k. There also exist K3-WORM colorable graphs which have a K3-WORM coloring with...
In this paper we present logics about stable and unstable versions of several well-known relations from mereology: part-of, overlap and underlap. An intuitive semantics is given for the stable and unstable relations, describing them as dynamic counterparts of the base mereological relations. Stable relations are described as ones that always hold, while unstable relations hold sometimes. A set of first-order sentences is provided to serve as axioms for the stable and unstable relations, and representation...
We show that the size of a Las Vegas automaton and the size of a complete, minimal deterministic automaton accepting a regular language are polynomially related. More precisely, we show that if a regular language is accepted by a Las Vegas automaton having states such that the probability for a definite answer to occur is at least , then , where is the number of the states of the minimal deterministic automaton accepting . Earlier this result has been obtained in [2] by using a reduction...
We show that the size of a Las Vegas automaton
and the size of a complete, minimal deterministic
automaton accepting a regular
language are polynomially related. More precisely, we show
that if a regular language L is accepted by a
Las Vegas automaton having r states such that
the probability for a definite answer to occur is at least p,
then r ≥ np, where n is the number of the states
of the minimal deterministic automaton accepting L.
Earlier this result has been obtained
in [2] by using a reduction...
An (f, g)-semi-matching in a bipartite graph G = (U ∪ V,E) is a set of edges M ⊆ E such that each vertex u ∈ U is incident with at most f(u) edges of M, and each vertex v ∈ V is incident with at most g(v) edges of M. In this paper we give an algorithm that for a graph with n vertices and m edges, n ≤ m, constructs a maximum (f, g)-semi-matching in running time O(m ⋅ min [...] ) Using the reduction of [5] our result on maximum (f, g)-semi-matching problem directly implies an algorithm for the optimal...
We propose a new way of characterizing the complexity of online problems.
Instead of measuring the degradation of the output quality caused by the ignorance
of the future we choose to quantify the amount of additional global information
needed for an online algorithm to solve the problem optimally. In our model, the
algorithm cooperates with an oracle that can see the whole input. We define
the advice complexity of the problem to be the minimal number of bits
(normalized per input request, and...
We investigate the complexity of several problems concerning Las Vegas finite automata. Our results are as follows.
(1) The membership problem for Las Vegas finite automata is in NL.
(2) The nonemptiness and inequivalence problems for Las Vegas finite automata are NL-complete.
(3) Constructing for a given Las Vegas finite automaton a minimum state deterministic finite automaton is in NP.
These results provide partial answers to some open problems posed by Hromkovič
and Schnitger [Theoret....
A property of n-vertex graphs is called evasive if every algorithm testing this property by asking questions of the form “is there an edge between vertices u and v” requires, in the worst case, to ask about all pairs of vertices. Most “natural” graph properties are either evasive or conjectured to be such, and of the few examples of nontrivial nonevasive properties scattered in the literature the smallest one has n = 6. We exhibit a nontrivial, nonevasive property of 5-vertex graphs and show that...
We study the problem of scheduling jobs on a serial batching machine to minimize total tardiness. Jobs of the same batch start and are completed simultaneously and the length of a batch equals the sum of the processing times of its jobs. When a new batch starts, a constant setup time occurs. This problem s-batch is known to be NP-Hard in the ordinary sense. In this paper we show that it is solvable in pseudopolynomial time by dynamic programming.
We study the problem of scheduling jobs on a serial batching machine
to minimize total tardiness. Jobs of the same batch start and are
completed simultaneously and the length of a batch equals the sum of
the processing times of its jobs. When a new batch starts, a constant
setup time s occurs. This problem 1|s-batch
| ∑Ti is
known to be NP-Hard in the ordinary sense. In this paper we show that
it is solvable in pseudopolynomial time by dynamic programming.
We consider, for a positive integer , induced subgraphs in which each component has order at most . Such a subgraph is said to be -divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a -divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for -coloring...
We show that the decision problem for p-reinforcement, p-total rein- forcement, total restrained reinforcement, and k-rainbow reinforcement are NP-hard for bipartite graphs.
In the Shapley-Scarf economy each agent is endowed with one unit of an indivisible good (house) and wants to exchange it for another, possibly the most preferred one among the houses in the market. In this economy, core is always nonempty and a core allocation can be found by the famous Top Trading Cycles algorithm. Recently, a modification of this economy, containing Q >= 2 types of goods (say, houses and cars for Q=2) has been introduced. We show that if the number of agents is 2, a complete...
We study hardness of approximating several minimaximal and maximinimal NP-optimization problems related to the minimum linear ordering problem (MINLOP). MINLOP is to find a minimum weight acyclic tournament in a given arc-weighted complete digraph. MINLOP is APX-hard but its unweighted version is polynomial time solvable. We prove that MIN-MAX-SUBDAG problem, which is a generalization of MINLOP and requires to find a minimum cardinality maximal acyclic subdigraph of a given digraph, is, however,...
We study
hardness of approximating several minimaximal and maximinimal NP-optimization
problems related to the minimum linear ordering problem (MINLOP). MINLOP is
to find a minimum weight acyclic tournament in a given arc-weighted complete
digraph. MINLOP is APX-hard but its unweighted version is polynomial time
solvable. We prove that MIN-MAX-SUBDAG problem, which is a generalization of
MINLOP and requires to find a minimum cardinality maximal acyclic subdigraph
of a given digraph, is, however,...
Currently displaying 41 –
60 of
86