Search

For a finite set V of elements, a confluent system is a set system (V , C ⊆ 2 V) such that every three sets X , Y , Z ∈ C with Z ⊆ X ∩ Y implies X ∪ Y ∈ C , where we call a set C ∈ C a component. We assume that two oracles L 1 and L 2 are available, where given two subsets X , Y ⊆ V , L 1 returns a maximal component C ∈ C with X ⊆ C ⊆ Y ; and given a set Y ⊆ V , L 2 returns all maximal components C ∈ C with C ⊆ Y . Given a set I of items and a function σ : V → 2 I in a confluent system, a component C ∈ C is called a solution (or support-closed) if the set of common items in C is inclusively maximal; i.e., ⋂ v ∈ C σ (v) ⊋ ⋂ v ∈ X σ (v) for any component X ∈ C with C ⊊ X . We prove that there exists an algorithm of enumerating all solutions in polynomial delay and in polynomial space. The proposed algorithm yields polynomial-delay and polynomial-space algorithms for enumerating connectors in an attributed graph (i.e., a graph such that each vertex is assigned items) and for enumerating all subgraphs with various types of connectivities such as all k-edge/vertex-connected induced subgraphs and all k-edge/vertex-connected spanning subgraphs in a given undirected/directed graph for a fixed k. [ABSTRACT FROM AUTHOR]

A graph is called a 1-planar graph, if it admits a 1-plane embedding (i.e., an embedding with at most one crossing per edge). Thomassen characterized forbidden configuration for straight-line drawings of 1-plane graphs [Thomassen (1988) [38] ]. In this paper, we investigate the problem of re-embedding a 1-plane graph (i.e., 1-planar graph with a given 1-planar embedding) to admit a straight-line drawing, preserving the original set of edge crossings of 1-plane graphs. More specifically, we characterize forbidden configurations such that a given 1-plane graph can be re-embedded into a straight-line drawable 1-plane embedding if and only if it does not contain the configurations. We present a linear-time algorithm for computing a straight-line drawable 1-plane re-embedding, if one exists, or finding the forbidden configuration, otherwise. To design a linear-time algorithm, we exploit a data structure called an inclusion-forest that summarizes the inclusion relationships between non-intersecting cycles of a plane graph. [ABSTRACT FROM AUTHOR]

A graph G is called a pairwise compatibility graph (PCG, for short) if it admits a tuple (T , w , d min , d max) of a tree T whose leaf set is equal to the vertex set of G, a non-negative edge weight w, and two non-negative reals d min ≤ d max such that G has an edge between two vertices u , v ∈ V if and only if the distance between the two leaves u and v in the weighted tree (T, w) is in the interval [ d min , d max ] . The tree T is also called a witness tree of the PCG G. How to recognize PCGs is a wide-open problem in the literature. This paper gives a complete characterization for a graph to be a star-PCG (a PCG that admits a star as its witness tree), which provides us the first polynomial-time algorithm for recognizing star-PCGs. [ABSTRACT FROM AUTHOR]

Abstract A planar graph can be drawn without edge crossings in the plane. It is well known that testing planarity of a graph can be solved in linear time. A graph is 1-planar, if it admits a 1-planar embedding, where each edge has at most one crossing. Testing 1-planarity of a graph is known to be NP-complete. This paper initiates the problem of testing 2-planarity of a graph, in particular, testing "full-outer-2-planarity" of a graph. A graph is outer- k -planar for an integer k ≥ 0 , if it admits an outer- k -planar embedding , that is, every vertex is on the outer boundary and no edge has more than k crossings. A graph is full-outer- k -planar , if it admits a full-outer- k -planar embedding , that is, an outer- k -planar embedding such that no crossing appears along the outer boundary. We present several structural properties of triconnected outer-2-planar graphs and full-outer-2-planar graphs, and prove that every triconnected full-outer-2-planar graph has a constant number of full-outer-2-planar embeddings. Based on these properties, we present linear-time algorithms for testing full-outer-2-planarity of a graph G , where G is connected, biconnected or triconnected. The algorithm also produces a full-outer-2-planar embedding of a graph, if it exists. Moreover, we show that every outer- k -planar embedding admits a straight-line drawing. [ABSTRACT FROM AUTHOR]

We consider a set system (V , C ⊆ 2 V) on a finite set V of elements, where we call a set C ∈ C a component. We assume that two oracles L 1 and L 2 are available, where given two non-empty subsets X ⊆ Y ⊆ V , L 1 (X , Y) returns a maximal component C ∈ C with X ⊆ C ⊆ Y ; and given a set Y ⊆ V , L 2 (Y) returns all maximal components C ∈ C with C ⊆ Y. Given a system (V , C) along with a set I of items and a function σ : V → 2 I , a component C ∈ C is called a solution if the set of common items in C is inclusively maximal; i.e., ⋂ v ∈ C σ (v) ⊋ ⋂ v ∈ X σ (v) for any component X ∈ C with C ⊊ X. We prove that there exists an algorithm of enumerating all solutions (or all components) in delay bounded by a polynomial with respect to the input size; an upper bound on the number of maximal components that is returned by L 2 ; and the running times of the oracles. [ABSTRACT FROM AUTHOR]

We show that the maximum independent set problem on an n -vertex graph can be solved in 1.1996 n n O ( 1 ) time and polynomial space, which even is faster than Robson's 1.2109 n n O ( 1 ) -time exponential-space algorithm published in 1986. We also obtain improved algorithms for MIS in graphs with maximum degree 6 and 7, which run in time of 1.1893 n n O ( 1 ) and 1.1970 n n O ( 1 ) , respectively. Our algorithms are obtained by using fast algorithms for MIS in low-degree graphs in a hierarchical way and making a careful analysis on the structure of bounded-degree graphs. [ABSTRACT FROM AUTHOR]

In this paper, we study the parameterized complexity of the problems of partitioning the vertex set of a graph into two parts V A and V B such that V A induces a graph with degree at most a (resp., an a -regular graph) and V B induces a graph with degree at most b (resp., a b -regular graph). These two problems are called Upper-Degree-Bounded Bipartition and Regular Bipartition , respectively. When a = b = 0 , the two problems become the polynomially solvable problem of checking the bipartition of a graph. When a = 0 and b = 1 , Regular Bipartition becomes a well-known NP-hard problem, called Dominating Induced Matching . In this paper, firstly we prove that the two problems are NP-complete with any nonnegative integers a and b except a = b = 0 . Secondly, we show the fixed-parameter tractability of these two problems with parameter k = | V A | being the size of one part of the bipartition by deriving several problem kernels for them and constrained versions of them. [ABSTRACT FROM AUTHOR]

The paper presents an $$O^*(1.2312^n)$$ -time and polynomial-space algorithm for the traveling salesman problem in an $$n$$ -vertex graph with maximum degree 3. This improves all previous time bounds of polynomial-space algorithms for this problem. Our algorithm is a simple branch-and-search algorithm with only one branch rule designed on a cut-circuit structure of a graph induced by unprocessed edges. To improve a time bound by a simple analysis on measure and conquer, we introduce an amortization scheme over the cut-circuit structure by defining the measure of an instance to be the sum of not only weights of vertices but also weights of connected components of the induced graph. [ABSTRACT FROM AUTHOR]

The paper presents a 1.692 n-time polynomial-space algorithm for the traveling salesman problem in an n-vertex edge-weighted graph with maximum degree 4, which improves the previous results of the 1.890 n-time polynomial-space algorithm by Eppstein and the 1.733 n-time exponential-space algorithm by Gebauer. [ABSTRACT FROM AUTHOR]

The maximum independent set problem is a basic NP-hard problem and has been extensively studied in exact algorithms. The maximum independent set problems in low-degree graphs are also important and may be bottlenecks of the problem in general graphs. In this paper, we present a 1.173 6 n n O ( 1 ) -time exact algorithm for the maximum independent set problem in an n -vertex graph with degree bounded by 5 , improving the previous running time bound of 1.189 5 n n O ( 1 ) . In our algorithm, we show that the graph after applying reduction rules always has a good local structure branching on which will effectively reduce the instance. Based on this, we obtain an improved algorithm without introducing a large number of branching rules. [ABSTRACT FROM AUTHOR]

A dominating induced matching , also called an efficient edge domination , of a graph G = ( V , E ) with n = | V | vertices and m = | E | edges is a subset F ⊆ E of edges in the graph such that no two edges in F share a common endpoint and each edge in E ∖ F is incident with exactly one edge in F . It is NP-hard to decide whether a graph admits a dominating induced matching or not. In this paper, we design a 1.146 7 n n O ( 1 ) -time exact algorithm for this problem, improving all previous results. This problem can be redefined as a partition problem that is to partition the vertex set of a graph into two parts I and F , where I induces an independent set (a 0-regular graph) and F induces a perfect matching (a 1-regular graph). After giving several structural properties of the problem, we show that the problem always contains some “good vertices,” branching on which by including them to either I or F we can effectively reduce the graph. This leads to a fast exact algorithm to this problem. [ABSTRACT FROM AUTHOR]

In this paper, we present a new exact algorithm for the Edge Dominating Set problem, and analyze its running time by the Measure and Conquer method. Our algorithm runs in 1.3160 n n O ( 1 ) time for a graph with n vertices, which is the currently fastest known time for the Edge Dominating Set problem. By designing new branching rules based upon conceptually simple local structures, which we call clique-producing vertices and cycles, we obtain an algorithm that is simpler than the previously fastest known algorithm and has an improved time bound as well. [ABSTRACT FROM AUTHOR]

Background: The enumeration of chemical graphs (molecular graphs) satisfying given constraints is one of the fundamental problems in chemoinformatics and bioinformatics because it leads to a variety of useful applications including structure determination and development of novel chemical compounds. Results: We consider the problem of enumerating chemical graphs with monocyclic structure (a graph structure that contains exactly one cycle) from a given set of feature vectors, where a feature vector represents the frequency of the prescribed paths in a chemical compound to be constructed and the set is specified by a pair of upper and lower feature vectors. To enumerate all tree-like (acyclic) chemical graphs from a given set of feature vectors, Shimizu et al. and Suzuki et al. proposed efficient branch-and-bound algorithms based on a fast tree enumeration algorithm. In this study, we devise a novel method for extending these algorithms to enumeration of chemical graphs with monocyclic structure by designing a fast algorithm for testing uniqueness. The results of computational experiments reveal that the computational efficiency of the new algorithm is as good as those for enumeration of tree-like chemical compounds. Conclusions: We succeed in expanding the class of chemical graphs that are able to be enumerated efficiently. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we present an -time algorithm to decide whether a graph of maximum degree has an edge dominating set of size at most or not, which is based on enumeration of vertex covers and improves all previous results on this problem. We first enumerate partial vertex covers of size at most and then construct an edge dominating set based on each vertex cover to find a required edge dominating set. To effectively enumerate vertex covers, we adopt a branch-and-reduce method, and use some techniques, such as ‘pseudo-cliques’ and ‘amortized transfer of cliques,’ to analyze the running time bound. [Copyright &y& Elsevier]

Abstract: We present an -time algorithm for finding a maximum independent set in an -vertex graph with degree bounded by 3, which improves all previous running time bounds for this problem. Our approach has the following two features. Without increasing the number of reduction/branching rules to get an improved time bound, we first successfully extract the essence from the previously known reduction rules such as domination, which can be used to get simple algorithms. More formally, we introduce a procedure for computing “confining sets”, which unifies several known reducible subgraphs and covers new reducible subgraphs. Second we identify those instances that generate the worst recurrence among all recurrences of our branching rules as “bottleneck instances” and prove that bottleneck instances cannot appear consecutively after each branching operation. [Copyright &y& Elsevier]

Abstract: A star-shaped drawing of a plane graph is a straight-line drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. In this paper, given a biconnected plane graph with fixed plane embedding and a prescribed set of concave corners, we study the following two problems on star-shaped drawings. First, we consider the problem of finding a star-shaped drawing of such that only prescribed corners are allowed to become concave corners in . More specifically, we characterize a necessary and sufficient condition for a subset of prescribed corners to admit such a star-shaped drawing of . Our characterization includes Thomassen’s characterization of biconnected plane graphs with a prescribed boundary that have convex drawings . We also give a linear-time testing algorithm to test such conditions. Next, given a non-negative cost for each corner in , we show that a star-shaped drawing of with the minimum cost can be found in linear-time, where the cost of a drawing is defined by the sum of costs of concave corners in the drawing. [Copyright &y& Elsevier]

A star-shaped drawing of a graph is a straight-line drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. In this paper, we consider the problem of finding a star-shaped drawing of a biconnected planar graph with the minimum number of concave corners. We first show new structural properties of planar graphs to derive a lower bound on the number of concave corners. Based on the lower bound, we prove that the problem can be solved in linear time by presenting a linear-time algorithm for finding a best plane embedding of a biconnected planar graph with the minimum number of concave corners. This is in spite of the fact that a biconnected planar graph may have an exponential number of different plane embeddings. [ABSTRACT FROM AUTHOR]

In 1922, Steinitz's theorem gave a complete characterization of the topological structure of the vertices, edges, and faces of convex polyhedra as triconnected planar graphs. In this paper, we generalize Steinitz's theorem to non-convex polyhedra. More specifically, we introduce a new class of polyhedra, wider than convex polyhedra, called upward star-shaped polyhedra and spherical polyhedra, and present graph-theoretic characterization for both polyhedra. Upward star-shaped polyhedra are polyhedra where each face is star-shaped, all faces except the bottom face are visible from a view point, and any two faces sharing two vertices are non-coplanar. Spherical polyhedra are non-singular, non-coplanar polyhedra with no holes. We first present a graph-theoretic characterization of upward star-shaped polyhedra, i.e., characterization of upward star-shaped polyhedral graphs, which are the vertex-edge graphs (or 1-skeleton) of the upward star-shaped polyhedra. Roughly speaking, they correspond to biconnected planar graphs with special conditions. The proof of the characterization leads to an algorithm that constructs an upward star-shaped polyhedron with n vertices in O( n) time. Moreover, one can test whether a given plane graph is an upward star-shaped polyhedral graph in linear time. We then present a graph-theoretic characterization of spherical polyhedra for planar cubic graphs, and planar graphs with maximum face size 4. We also formally define the Polyhedra Realizability Problem, and discuss its reducibility. Our result is the first graph-theoretic characterization of non-convex polyhedra, which solves an open problem posed by Grünbaum (Discrete Math. 307(3-5), 445-463, ), and a generalization of Steinitz's theorem (Polyeder und Raumeinteilungen, ), which characterized convex polyhedra as triconnected planar graphs. [ABSTRACT FROM AUTHOR]

Abstract: A cop–robber guarding game is played by the robber-player and the cop-player on a graph with a partition and of the vertex set. The robber-player starts the game by placing a robber (her pawn) on a vertex in , followed by the cop-player who places a set of cops (her pawns) on some vertices in . The two players take turns in moving their pawns to adjacent vertices in . The cop-player moves the cops within to prevent the robber-player from moving the robber to any vertex in . The robber-player wins if it gets a turn to move the robber onto a vertex in on which no cop situates, and the cop-player wins otherwise. The problem is to find the minimum number of cops that admits a winning strategy to the cop-player. It has been shown that the problem is polynomially solvable if induces a path, whereas it is NP-complete if induces a tree. In this paper, we show that the problem remains NP-complete even if induces a 3-star and that the problem is polynomially solvable if induces a cycle. [ABSTRACT FROM AUTHOR]

Background: Enumeration of chemical graphs satisfying given constraints is one of the fundamental problems in chemoinformatics and bioinformatics since it leads to a variety of useful applications including structure determination of novel chemical compounds and drug design. Results: In this paper, we consider the problem of enumerating all tree-like chemical graphs from a given set of feature vectors, which is specified by a pair of upper and lower feature vectors, where a feature vector represents the frequency of prescribed paths in a chemical compound to be constructed. This problem can be solved by applying the algorithm proposed by Ishida et al. to each single feature vector in the given set, but this method may take much computation time because in general there are many feature vectors in a given set. We propose a new exact branch-and-bound algorithm for the problem so that all the feature vectors in a given set are handled directly. Since we cannot use the bounding operation proposed by Ishida et al. due to upper and lower constraints, we introduce new bounding operations based on upper and lower feature vectors, a bond constraint, and a detachment condition. Conclusions: Our proposed algorithm is useful for enumerating tree-like chemical graphs with given upper and lower bounds on path frequencies. [ABSTRACT FROM AUTHOR]

Symmetry is one of the most important aesthetic criteria in Graph Drawing which can reveal the hidden structure in the graph. Convex drawing is a straight-line drawing where every facial cycle is drawn as a convex polygon. In this paper, we prove that given an internally triconnected plane graph with symmetries, there exists a convex drawing of the graph which displays the given symmetries. We present a linear-time algorithm for constructing symmetric convex drawings of internally triconnected planar graphs. This is an extension of a classical result due to Tutte (Proc. Lond. Math. Soc. 10(3):304–320, ; Proc. Lond. Math. Soc. 13:743–768, ) who proved that every triconnected plane graph with a given convex polygon as a boundary admits a convex drawing. Note that Tutte’s barycenter mapping method can be implemented in O( n1.5) time and O( nlog n) space at best (Lipton et al. in SIAM J. Numer. Anal. 16:346–358, ). Our divide and conquer algorithm explicitly exploits the fundamental properties of symmetric drawing, which consists of congruent drawings of isomorphic subgraphs. We first find an isomorphic subgraph of a given symmetric plane graph, and compute an angle-constrained convex drawing of the subgraph. Finally, a symmetric convex drawing of the given graph is constructed by merging repetitive copies of the congruent drawings of isomorphic subgraphs. For this purpose, we define a new problem of angle-constrained convex drawing of plane graphs, where some of outer vertices have angle constraints. Our results also imply that there is a linear-time algorithm that constructs maximally symmetric convex drawings of triconnected planar graphs. Previous algorithm (Hong et al. in Discrete Comput. Geom. 36:283–311, ) constructs symmetric drawings of triconnected planar graphs with straight-lines. [ABSTRACT FROM AUTHOR]

We study a crossing minimization problem of drawing a bipartite graph with a radial drawing of two orbits. Radial drawings are one of well-known drawing conventions in social network analysis and visualization, in particular, displaying centrality indices of actors (Wasserman and Faust, Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge, ). The main problem in this paper is called the one-sided radial crossing minimization, if the positions of vertices in the outer orbit are fixed. The problem is known to be NP-hard (Bachmaier, IEEE Trans. Vis. Comput. Graph. 13, 583–594, ), and a number of heuristics are available (Bachmaier, IEEE Trans. Vis. Comput. Graph. 13, 583–594, ). However, there is no approximation algorithm for the crossing minimization problem in radial drawings. We present the first polynomial time constant-factor approximation algorithm for the one-sided radial crossing minimization problem. [ABSTRACT FROM AUTHOR]

Abstract: A straight-line planar drawing of a plane graph is called a convex drawing if every facial cycle is drawn as a convex polygon. Convex drawings of graphs is a well-established aesthetic in graph drawing, however not all planar graphs admit a convex drawing. Tutte [W.T. Tutte, Convex representations of graphs, Proc. of London Math. Soc. 10 (3) (1960) 304–320] showed that every triconnected plane graph admits a convex drawing for any given boundary drawn as a convex polygon. Thomassen [C. Thomassen, Plane representations of graphs, in: Progress in Graph Theory, Academic Press, 1984, pp. 43–69] gave a necessary and sufficient condition for a biconnected plane graph with a prescribed convex boundary to have a convex drawing. In this paper, we initiate a new notion of star-shaped drawing of a plane graph as a straight-line planar drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. A star-shaped drawing is a natural extension of a convex drawing, and a new aesthetic criteria for drawing planar graphs in a convex way as much as possible. We give a sufficient condition for a given set A of corners of a plane graph to admit a star-shaped drawing whose concave corners are given by the corners in A, and present a linear time algorithm for constructing such a star-shaped drawing. [Copyright &y& Elsevier]

We consider the following network design problem; Given a vertex set V with a metric cost c on V, an integer k≥1, and a degree specification b, find a minimum cost k-edge-connected multigraph on V under the constraint that the degree of each vertex v∈ V is equal to b( v). This problem generalizes metric TSP. In this paper, we show that the problem admits a ρ-approximation algorithm if b( v)≥2, v∈ V, where ρ=2.5 if k is even, and ρ=2.5+1.5/ k if k is odd. We also prove that the digraph version of this problem admits a 2.5-approximation algorithm and discuss some generalization of metric TSP. [ABSTRACT FROM AUTHOR]

Abstract: We consider orthogonal drawings of a plane graph with specified face areas. For a natural number , a -gonal drawing of is an orthogonal drawing such that the boundary of is drawn as a rectangle and each inner face is drawn as a polygon with at most corners whose area is equal to the specified value. In this paper, we show that every slicing graph with a slicing tree and a set of specified face areas admits a 10-gonal drawing such that the boundary of each slicing subgraph that appears in is also drawn as a polygon with at most 10 corners. Such a drawing can be found in linear time. [Copyright &y& Elsevier]

Abstract: For a graph , a detachment operation at a vertex transforms the graph into a new graph by splitting the vertex into several vertices in such a way that the original graph can be obtained by contracting all the split vertices into a single vertex. A graph obtained from a given graph by applying detachment operations at several vertices is called a detachment of graph . While detachment operations may decrease the connectivity of graphs, there are several works on conditions for preserving the connectivity. In this paper, we present necessary and sufficient conditions for a given graph/digraph to have an Eulerian detachment that satisfies a given local edge-connectivity requirement. We also discuss conditions for the detachment to be loopless. [Copyright &y& Elsevier]

Abstract: In this paper, we study a new problem of convex drawing of planar graphs with non-convex boundary constraints, and call a drawing in which every inner-facial cycle is drawn as a convex polygon an inner-convex drawing. It is proved that every triconnected plane graph with the boundary fixed with a star-shaped polygon whose kernel has a positive area admits an inner-convex drawing. We also prove that every four-connected plane graph whose boundary is fixed with a crown-shaped polygon admits an inner-convex drawing. We present linear time algorithms to construct inner-convex drawings for both cases. [Copyright &y& Elsevier]

In this paper, we study a problem of finding a vehicle scheduling to process a set of jobs which are located in an asymmetric metric space. Each job has a positive handling time , a time window , and a benefit . We consider the following two problems: MAX-VSP asks to find a schedule for a single vehicle to process a subset of jobs with the maximum benefit; and MIN-VSP asks to find a schedule to process all given jobs with the minimum number of vehicles. We first give an time algorithm that delivers a -approximate solution to MAX-VSP, where and is the maximum number of jobs that can be processed by the vehicle after processing a job and before visiting the processed job again by deadline . We then present an time algorithm that delivers a -approximate solution to MIN-VSP, where is the th harmonic number. [Copyright &y& Elsevier]

Abstract: Let be a connected graph such that each edge is weighted by nonnegative real . Let be a vertex designated as a source, be a positive integer, and be a set of terminals. The capacitated multicast tree routing problem (CMTR) asks to find a partition of and a set of trees of such that consists of at most terminals and each spans . The objective is to minimize , where denotes the sum of weights of all edges in . In this paper, we propose a -approximation algorithm to the CMTR, where is the best achievable approximation ratio for the Steiner tree problem. [Copyright &y& Elsevier]

In this paper, the author explains the recent evolution of algorithms for minimum partitioning problems in graphs. When the set of vertices of a graph having non-negative weights for edges is divided into k subsets, the set of edges for which both endpoints are contained in different subsets is called a k-way cut or k-cut. The problem of obtaining the k-way cut that minimizes the sum of the weights is an important research topic that appears in many practical applications such as VLSI design. In this paper, the author introduces recent results including cases in which sets of terminals or sets of terminal pairs that are to be separated are further specified in this problem and cases in which the objects to be partitioned are extended from graphs to hypergraphs or submodular set functions. © 2007 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 90(10): 63– 78, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.20341 [ABSTRACT FROM AUTHOR]

Abstract: In a graph, a cluster is a set of vertices, and two clusters are said to be non-intersecting if they are disjoint or one of them is contained in the other. A clustered graph C consists of a graph G and a set of non-intersecting clusters. In this paper, we assume that C has a compound planar drawing and each cluster induces a biconnected subgraph. Then we show that such a clustered graph admits a drawing in the plane such that (i) edges are drawn as straight-line segments with no edge crossing and (ii) the boundary of the biconnected subgraph induced by each cluster is a convex polygon. [Copyright &y& Elsevier]

Abstract: Given a rectangle R with area and a set of n positive reals with , we consider the problem of dissecting R into n rectangles with area so that the set of resulting rectangles minimizes an objective function such as the sum of the perimeters of the rectangles in , the maximum perimeter of the rectangles in , and the maximum aspect ratio of the rectangles in , where we call the problems with these objective functions PERI-SUM, PERI-MAX and ASPECT-RATIO, respectively. We propose an time algorithm that finds a dissection of R that is a 1.25-approximate solution to PERI-SUM, a -approximate solution to PERI-MAX, and has an aspect ratio at most , where denotes the aspect ratio of R. [Copyright &y& Elsevier]

Abstract: For an undirected multigraph , let be a positive integer weight function on V. For a positive integer k, G is called -connected if any two vertices remain connected after removal of any pair of a vertex subset and an edge subset such that . The -connectivity is an extension of several common generalizations of edge-connectivity and vertex-connectivity. Given a -connected graph G, we show that a -connected spanning subgraph of G with edges can be found in linear time by using MA orderings. We also show that properties on removal cycles and preservation of minimum cuts can be extended in the -connectivity. [Copyright &y& Elsevier]

Abstract: Let be a hypergraph with a node set , a hyperedge set , and real edge-weights for . Given a convex n-gon P in the plane with vertices which are arranged in this order clockwisely, let each node correspond to the vertex and define the area of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For , a convex three-cut of N is , , and its size in H is defined as the sum of weights of edges such that e contains at least one node from each of , and . We show that the following two conditions are equivalent: [•] for all convex n-gons P. [•] for all convex three-cuts . From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and satisfy “ for all convex n-gons P” is immediately obtained. [Copyright &y& Elsevier]

Let R be a rectangle with given area a(R), height h(R) and width w(R), and r1, r2, ..., rn be n soft rectangles, where we mean by a soft rectangle a rectangle r whose area a(r) is prescribed but whose aspect ratio ρ(r) is allowed to be changed. In this paper, we consider the problem of packing n soft rectangles r1, r2, ..., rn into R. We prove that, if a(R) ≥ Σ1≤i≤n a(ri) + 0.10103amax and amax ≤ 3(min{h(R), w(R)})2 hold for a amax = max1≤i≤n a(ri), then these n soft rectangles can be packed inside R so that the apect ratio of each rectangle ri is at most 3. [ABSTRACT FROM AUTHOR]

Abstract: Let be a connected graph such that edges and vertices are weighted by nonnegative reals. Let p be a positive integer. The minmax subtree cover problem (MSC) asks to find a pair of a partition of V and a set of p subtrees , each containing so as to minimize the maximum cost of the subtrees, where the cost of is defined to be the sum of the weights of edges in and the weights of vertices in . In this paper, we propose an time -approximation algorithm for the MSC when G is a cactus. [Copyright &y& Elsevier]

Abstract: Given two disjoint subsets and of nodes in a 3-connected graph with a node set V and an arc set E, where and are even numbers, it is known that V can be partitioned into two sets and such that the graphs induced by and are both connected and holds for each . An time and space algorithm for finding such a bipartition has been proposed based on a geometric argument, where G is embedded in the plane and the node set is bipartitioned by a ham-sandwich cut on the embedding. A naive implementation of the algorithm, however, requires high precision real arithmetic to distinguish two close points in a large set of points on . In this paper, we propose an time and space algorithm to the problem. The new algorithm, which remains to be based on the geometric embedding, can construct a solution purely combinatorially in the sense that it does not require computing actual embedded points in and thereby no longer needs to store any real number for embedded points. Although the new algorithm seems to need more space complexity, it can be implemented only with linked lists such that each element stores an integer in . [Copyright &y& Elsevier]

Abstract: Given a simple connected graph and a set R of pairs of vertices, we consider the problem of augmenting G by a smallest set F of new edges such that the resulting graph remains simple and has at least two internally disjoint paths between u and v for each pair . The problem is known to be NP-hard, and a -approximation algorithm has been obtained so far. In this paper, we introduce new stronger lower bounds on the optimal value, and propose an time -approximation algorithm to the problem. [Copyright &y& Elsevier]

Abstract: Given a bipartite graph , a 2-layered drawing consists of placing nodes in the first node set V on a straight line and placing nodes in the second node set W on a parallel line . For a given ordering of nodes in W on , the one-sided crossing minimization problem asks to find an ordering of nodes in V on so that the number of arc crossings is minimized. A well-known lower bound LB on the minimum number of crossings is obtained by summing up over all node pairs , where denotes the number of crossings generated by arcs incident to u and when u precedes in an ordering. In this paper, we prove that there always exists a solution whose crossing number is at most if the minimum degree of a node in V is at least 5. [Copyright &y& Elsevier]

Given a system (V,T,f,k), whereVis a finite set,is a submodular function andk=2 is an integer, the generalmultiway partition problem(MPP) asks to find ak-partition={V1,V2,...,V k} ofVthat satisfiesfor alliand minimizesf(V1)+f(V2)+···+f(V k), whereis ak-partition ofhold. MPP formulation captures a generalization in submodular systems of many NP-hard problems such ask-way cut,multiterminal cut,target splitand their generalizations in hypergraphs. This paper presents a simple and unified framework for developing and analyzing approximation algorithms for various MPPs. [ABSTRACT FROM AUTHOR]

Given a system (V,T,f,k) where V is a finite set, T⊆V, f:2V→R is a submodular function and k⩾2 is an integer, the multiway partition problem (MPP) asks to find a k-partition P={V1,V2,…,Vk} of V that satisfies Vi∩T≠ for all i and minimizes f(V1)+f(V2)+⋯+f(Vk). This formulation captures a generalization of many NP-hard partition problems in graphs or hypergraphs. Previously, the authors have shown a simple framework for approximating MPPs by greedily increasing the size of partition by one. In this paper, we show that, if T=V, improved guarantees are available by greedily increasing the size by two. We also show polynomial time implementations for several problem classes. [Copyright &y& Elsevier]

Given an edge-weighted tree T and an integer p⩾1, the minmax p-traveling salesmen problem on a tree T asks to find p tours such that the union of the p tours covers all the vertices. The objective is to minimize the maximum of length of the p tours. It is known that the problem is NP-hard and has a (2-2/(p+1))-approximation algorithm which runs in O(pp-1np-1) time for a tree with n vertices. In this paper, we consider an extension of the problem in which the set of vertices to be covered now can be chosen as a subset S of vertices and weights to process vertices in S are also introduced in the tour length. For the problem, we give an approximation algorithm that has the same performance guarantee, but runs in O((p-1)!·n) time. [Copyright &y& Elsevier]

In this paper, we consider a scheduling problem of vehicles on a path G with n vertices and n−1 edges. There are m identical vehicles. Each vertex in G has exactly one job. Any of the n jobs must be processed by some vehicle. Each job has a release time and a handling time. With the edges, symmetric travel times are associated. The problem asks to find an optimal schedule of the m vehicles that minimizes the maximum completion time of all the jobs. The problem is known to be NP-hard for any fixed m⩾2. In this paper, we show that the problem with a fixed m admits a polynomial time approximation scheme. Our algorithm can be extended to the case where G is a tree so that a polynomial time approximation scheme is obtained if m and the number of leaves in G are fixed. [Copyright &y& Elsevier]

Given a graph G and target values r(u,v) prescribed for each pair of vertices u and v, we consider the problem of augmenting G by a smallest set F of new edges such that the resulting graph G+F has at least r(u,v) internally disjoint paths between each pair of vertices u and v. We show that the problem is NP-hard even if for some constant k⩾2 G is (k−1)-vertex-connected and r(u,v)∈{0,k} holds for u,v∈V. We then give a linear time algorithm which delivers a 3/2-approximation solution to the problem with a connected graph G and r(u,v)∈{0,2}, u,v∈V. [Copyright &y& Elsevier]

In this paper, given a path G with n vertices v1,v2,…,vn and m identical vehicles, we consider a scheduling problem of the vehicles on the path. Each vertex vj in G has exactly one job j. Any of the n jobs must be served by some vehicle. Each job j has a release time rj and a handling time hj. A travel time we is associated with each edge e. The problem asks to find an optimal schedule of the m vehicles that minimizes the maximum completion time of all jobs. It is already known that the problem is NP-hard for any fixed m⩾2. In this paper, we first present an O(mn2) time 2-approximation algorithm to the problem, by using properties of optimal gapless schedules. We then give a nearly linear time algorithm that delivers a (2+ϵ)-approximation solution for any fixed ϵ>0. [Copyright &y& Elsevier]

Given a hypergraph with nonnegative costs on hyperedges, and a weakly supermodular function r : 2V→Z+, where V is the vertex set, we consider the problem of finding a minimum cost subset of hyperedges such that for every set S⊆V, there are at least r(S) hyperedges that have at least one but no all endpoints in S. This problem captures a hypergraph generalization of the survivable network design problem (SNDP), and also the element connectivity problem (ECP). We present a primal–dual algorithm with a performance guarantee of dmax+H(rmax), where dmax+ is the maximum degree of hyperedges of positive costs, rmax=maxS r(S), and H(k)=1+1/2+⋯+1/k+⋯+1/k. In particular, our result contains a 2H(rmax)-approximation algorithm for ECP, which gives an independent and complete proof for the result first obtained by Jain et al. (Proceedings of the SODA, 1999, p. 484–489). [Copyright &y& Elsevier]

Given a graph G=(V,E) and a tree T=(V,F) with E∩F=∅ such that G+T=(V,F∪E) is 2-edge-connected, we consider the problem of finding a smallest 2-edge-connected spanning subgraph (V,F∪E′) of G+T containing T. The problem, which is known to be NP-hard, admits a 2-approximation algorithm. However, obtaining a factor better than 2 for this problem has been one of the main open problems in the graph augmentation problem. In this paper, we show that the problem is (1.875+ϵ)-approximable in O(n1/2m+n2) time for any constant ϵ>0, where n=|V| and m=|E∪F|. [Copyright &y& Elsevier]

This paper surveys how the maximum adjacency (MA) ordering of the vertices in a graph can be used to solve various graph problems. We first explain that the minimum cut problem can be solved efficiently by utilizing the MA ordering. The idea is then extended to a fundamental operation of a graph, edge splitting. Based on this, the edge-connectivity augmentation problem for a given k (and also for the entire range of k) can be solved efficiently by making use of the MA ordering, where it is asked to add the smallest number of new edges to a given graph so that its edge-connectivity is increased to k. Other related topics are also surveyed. [Copyright &y& Elsevier]

We present a polynomial-time algorithm approximating the minimum weight edge dominating set problem within a factor of 2. It has been known that the problem is NP-hard but, when edge weights are uniform (so that the smaller the better), it can be efficiently approximated within a factor of 2. When general weights were allowed, however, very little had been known about its approximability, and only very recently was it shown to be approximable within a factor of 21/10 by reducing to the edge cover problem via LP relaxation. In this paper we extend the approach given therein, by studying more carefully polyhedral structures of the problem, and obtain an improved approximation bound as a result. While the problem considered is as hard to approximate as the weighted vertex cover problem is, the best approximation (constant) factor known for vertex cover is 2 even for the unweighted case, and has not been improved in a long time, indicating that improving our result would be quite difficult. [Copyright &y& Elsevier]

Abstract. For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k = 3, 4. The algorithm runs in O(n[sup k-1]F(n, m)) = O(mn[sup k] log(n[sup 2]/m)) time and O(n[sup 2]) space for k = 3, 4, where F(n, m) denotes the time bound required to solve the maximum flow problem in G. The bound for k = 3 matches the current best deterministic bound O(mn[sup 3]) for weighted graphs, but improves the bound O(mn[sup 3]) to O(n[sup 2] F(n, m)) = O(min(mn[sup 8/3], m[sup 3/2]n[sup 2])) for unweighted graphs. The bound O(mn[sup 4]) for k = 4 improves the previous best randomized bound O(n[sup 6]) (for m = o(n[sup 2])). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system. [ABSTRACT FROM AUTHOR]