Search

Block graphs are graphs in which every block (biconnected component) is a clique. A graph G = ( V , E ) is said to be an (unpartitioned) k -probe block graph if there exist k independent sets N i ⊆ V , 1 ≤ i ≤ k , such that the graph G ′ obtained from G by adding certain edges between vertices inside the sets N i , 1 ≤ i ≤ k , is a block graph; if the independent sets N i are given, G is called a partitioned k -probe block graph. In this paper we give good characterizations for 2 -probe block graphs, in both unpartitioned and partitioned cases. As an algorithmic implication, partitioned and unpartitioned probe block graphs can be recognized in linear time, improving a recognition algorithm of cubic time complexity previously obtained by Chang et al. (2011). [ABSTRACT FROM AUTHOR]

Given a source node and a node set, the node-to-set disjoint paths problem is to find disjoint paths from the source node to all nodes from the node set. In this paper, we propose an improved algorithm for the node-to-set disjoint paths problem on bi-rotator graphs. Our result improves the complexity of previous result from to , where n is the dimension of the input graph. [ABSTRACT FROM AUTHOR]

Block graphs are graphs in which every block (biconnected component) is a clique. A graph G = ( V , E ) is said to be an (unpartitioned) probe block graph if there exist an independent set N ⊆ V and some set E ′ ⊆ ( N 2 ) such that the graph G ′ = ( V , E ∪ E ′ ) is a block graph; if such an independent set N is given, G is called a partitioned probe block graph. In this note we give good characterizations for probe block graphs, in both unpartitioned and partitioned cases. As a result, partitioned and unpartitioned probe block graphs can be recognized in linear time. [ABSTRACT FROM AUTHOR]

Abstract: For a given graph , the interval completion problem of G is to find an edge set F such that the supergraph of G is an interval graph and is minimum. It has been shown that it is equivalent to the minimum sum cut problem, the profile minimization problem and a kind of graph searching problems. Furthermore, it has applications in computational biology, archaeology, and clone fingerprinting. In this paper, we show that it is NP-complete on split graphs and propose an efficient algorithm on primitive starlike graphs. [Copyright &y& Elsevier]

Abstract: Let be a class of graphs. A graph has -width if there are independent sets in such that can be embedded into a graph such that for every edge in which is not an edge in , there exists an such that both endvertices of are in . For the class of block graphs we show that graphs with -width at most 4 are perfect. We also show that -width is NP-complete and show that it is fixed-parameter tractable. For the class of complete graphs, similar results are also obtained. [Copyright &y& Elsevier]

Abstract: Given a class of graphs , a graph is a probe graph of if its vertices can be partitioned into two sets, , the probes, and an independent set , the nonprobes, such that can be embedded into a graph of by adding edges between certain vertices of . If the partition of the vertices into probes and nonprobes is part of the input, then we call the graph a partitioned probe graph of . In this paper, we provide a recognition algorithm for partitioned probe permutation graphs with time complexity , where is the number of vertices of the input graph. We show that a probe permutation graph has at most minimal separators. As a consequence, for probe permutation graphs there exist polynomial-time algorithms solving problems like treewidth and minimum fill-in. We also characterize those graphs for which the probe graphs must be weakly chordal. [Copyright &y& Elsevier]