Chen, Min Hahn, Geňa Raspaud, André Wang, Weifan
Published in
Journal of Combinatorial Optimization

A k-coloring of a graph G=(V,E) is a mapping c:V→{1,2,…,k}. The coloring c is injective if, for every vertex v∈V, all the neighbors of v are assigned with distinct colors. The injective chromatic number χi(G) of G is the smallest k such that G has an injective k-coloring. In this paper, we prove that every K4-minor free graph G with maximum degree ...

Li, Jianping Li, Weidong Wang, Lusheng
Published in
Journal of Combinatorial Optimization

Given a directed hypergraph H=(V,EH), we consider the problem of embedding all directed hyperedges on a weighted ring. The objective is to minimize the maximum congestion which is equal to the maximum product of the weight of a link and the number of times that the link is passed by the embedding. In this paper, we design a polynomial time approxim...

Zhou, Xiao Hikino, Takashi Nishizeki, Takao
Published in
Journal of Combinatorial Optimization

In a grid drawing of a planar graph, every vertex is located at a grid point, and every edge is drawn as a straight-line segment without any edge-intersection. It is known that every planar graph G of n vertices has a grid drawing on an (n−2)×(n−2) or (4n/3)×(2n/3) integer grid. In this paper we show that if a planar graph G has a balanced partitio...

Jou, Min-Jen
Published in
Journal of Combinatorial Optimization

A maximal independent set is an independent set that is not a proper subset of any other independent set. In this paper, we determine the second largest number of maximal independent sets among all graphs (respectively, connected graphs) of order n≥4 with at most one cycle. We also characterize those extremal graphs achieving these values.

Huang, Yuan-Zhen Chiang, Chun-Ying Huang, Liang-Hao Yeh, Hong-Gwa
Published in
Journal of Combinatorial Optimization

A variation of the classical channel assignment problem is to assign a radio channel which is a nonnegative integer to each radio transmitter so that “close” transmitters must receive different channels and “very close” transmitters must receive channels that are at least two channels apart. The goal is to minimize the span of a feasible assignment...

Luo, Wenchang Chen, Lin Zhang, Guochuan
Published in
Journal of Combinatorial Optimization

In this paper we consider two-machine flow shop scheduling with two agents. Two models are investigated. One is the weighted-sum optimization model and the other is the constrained optimization model. For the former, we show that it is weakly NP-hard and propose a fully polynomial time approximation scheme. For the latter, we also show the problem ...

Chen, Lei Lu, Changhong Zeng, Zhenbing
Published in
Journal of Combinatorial Optimization

Let G=(V,E) be a simple graph without isolated vertices. A set S⊆V is a paired-dominating set if every vertex in V−S has at least one neighbor in S and the subgraph induced by S contains a perfect matching. In this paper, we present a linear-time algorithm to determine whether a given vertex in a block graph is contained in all its minimum paired-d...

Courcelle, Bruno Gavoille, Cyril Kanté, Mamadou Moustapha
Published in
Journal of Combinatorial Optimization

We consider graph properties that can be checked from labels, i.e., bit sequences, of logarithmic length attached to vertices. We prove that there exists such a labeling for checking a first-order formula with free set variables in the graphs of every class that is nicely locally clique-width-decomposable. This notion generalizes that of a nicely l...

Deschinkel, Karine Touati, Sid-Ahmed-Ali Briais, Sébastien
Published in
Journal of Combinatorial Optimization

In this paper, we study the general problem of one-dimensional periodic task scheduling under storage requirement, irrespective of machine constraints. We have already presented in (Touati and Eisenbeis, Parallel Process. Lett. 14(2):287–313, 2004) a theoretical framework that allows an optimal optimisation of periodic storage requirement in a cycl...

Chen, Jing Hou, Xinmin Li, Ning
Published in
Journal of Combinatorial Optimization

Let k be a positive integer and let G be a graph with vertex set V(G). The total {k}-dominating function (T{k}DF) of a graph G is a function f from V(G) to the set {0,1,2,…,k}, such that for each vertex v∈V(G), the sum of the values of all its neighbors assigned by f is at least k. A set {f1,f2,…,fd} of pairwise different T{k}DFs of G with the prop...