An st-ordering of a graph G=(V,E) is an ordering v(1),v(2), horizontal ellipsis ,v(n) of its vertex set such that s = v(1),t = v(n) and every vertex vi with i=2,3, horizontal ellipsis ,n-1 has both a lower numbered an...
详细信息
An st-ordering of a graph G=(V,E) is an ordering v(1),v(2), horizontal ellipsis ,v(n) of its vertex set such that s = v(1),t = v(n) and every vertex vi with i=2,3, horizontal ellipsis ,n-1 has both a lower numbered and a higher numbered neighbor. Such orderings have played an important role in algorithms for planarity testing. It is well-known that every 2-connected graph has an st-ordering for every choice of distinct vertices s,t. An st-ordering of a graph G corresponds directly to a so-called bipolar orientation of G, that is, an acyclic orientation D of G in which s is the unique source and t is the unique sink. Clearly every bipolar orientation of a graph has an out-branching rooted at the source vertex and an in-branching rooted at the sink vertex. In this paper, we study graphs which admit a bipolar orientation that contains an out-branching and in-branching which are arc-disjoint (such an orientation is called good). A 2T-graph is a graph whose edge set can be decomposed into two edge-disjoint spanning trees. Clearly a graph has a good orientation if and only if it contains a spanning 2T-graph with a good orientation, implying that 2T-graphs play a central role. It is a well-known result due to Tutte and Nash-Williams, respectively, that every 4-edge-connected graph contains a spanning 2T-graph. Vertex-minimal 2T-graphs with at least two vertices, also known as generic circuits, play an important role in rigidity theory for graphs. Recently with Bessy and Huang we proved that every generic circuit has a good orientation. In fact, we may specify the roots of the two branchings arbitrarily as long as they are distinct. Using this, several results on good orientations of 2T-graphs were obtained. It is an open problem whether there exists a polynomial algorithm for deciding whether a given 2T-graph has a good orientation. Complex constructions of 2T-graphs with no good orientation were given in work by Bang-Jensen, Bessy, Huang and Kriesell (2021) indicating tha
Integer-valued elements of an integral submodular flow polyhedron Q are investigated which are decreasingly minimal (dec-min) in the sense that their largest component is as small as possible, within this, the second ...
详细信息
Integer-valued elements of an integral submodular flow polyhedron Q are investigated which are decreasingly minimal (dec-min) in the sense that their largest component is as small as possible, within this, the second largest component is as small as possible, and so on. As a main result, we prove that the set of dec-min integral elements of Q is the set of integral elements of another integral submodular flow polyhedron arising from Q by intersecting a face of Q with a box. Based on this description, we develop a strongly polynomial algorithm for computing not only a dec-min integer-valued submodular flow but even a cheapest one with respect to a linear cost-function. A special case is the problem of finding a strongly connected (or k-edge-connected) orientation of a mixed graph whose in-degree vector is decreasingly minimal. (c) 2022 Elsevier B.V. All rights reserved.
The longest cycle problem is the problem of finding a cycle with maximal vertices in a graph. Although it is solvable in polynomial time on few trivial graph classes, the longest cycle problem is well known as NP-comp...
详细信息
The longest cycle problem is the problem of finding a cycle with maximal vertices in a graph. Although it is solvable in polynomial time on few trivial graph classes, the longest cycle problem is well known as NP-complete. A lot of efforts have been devoted to the longest cycle problem. To the best of our knowledge however, there are no polynomial algorithms that can solve any of the non-trivial graph classes. Interval graphs, the intersection of chordal graphs and asteroidal triple-free graphs, are known to be the non-trial graph classes that have polynomial algorithm of the longest cycle problem. In 2009, K. Ioannidou, G.B. Mertzios and S.D. Nikolopoulos presented a polynomial algorithm for the longest path problem on interval graphs in Ioannidou et al. (2009) [19]. Inspired by their work, we investigate the longest cycle problem of interval graphs. In this paper, we present the first polynomial algorithm for the longest cycle problem on interval graphs. A dynamic programming approach is proposed in the polynomial algorithm that runs in O(n(8)) time, where n is the number of vertices of the input graph. Using a similar approach, we design a polynomial algorithm to solve the longest k-thick subgraph problem on interval graphs which will be presented in another separate work. According to the interesting properties of k-thick interval graphs that we discovered (e.g., an interval graph G is traceable if and only if G is 1-thick, G is hamiltonian if and only if G is 2-thick, G is hamiltonian connected if and only if G is 3-thick and so on), the algorithm presented in this paper can be important in studying the spanning connectivity on interval graphs. (C) 2021 Elsevier B.V. All rights reserved.
We study the complexity of deciding whether a given digraph D = (V, A) admits a partition (A1, A2) of its arc set such that each of the corresponding digraphs D1 = (V, A1) and D2 = (V, A2) satisfy some given prescribe...
详细信息
We study the complexity of deciding whether a given digraph D = (V, A) admits a partition (A1, A2) of its arc set such that each of the corresponding digraphs D1 = (V, A1) and D2 = (V, A2) satisfy some given prescribed property. We mainly focus on the following 15 properties: being bipartite, being connected, being strongly connected, being acyclic (spanning or not necessarily spanning), containing an in-branching, containing an outbranching, having some in-degree (or out-degree) conditions, satisfying some conditions on the number of arcs, being balanced (connected or not) or being a cycle. Combined with previous research, our work leads to a complete classification (in terms of being polynomial or NP-complete) of the complexity of 120 arc-partitioning problems on digraphs.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).
We study the following problem: for given integers d, k and graph G, can we obtain a graph with diameter d via at most k edge deletions? We determine the computational complexity of this and related problems for diffe...
详细信息
We study the following problem: for given integers d, k and graph G, can we obtain a graph with diameter d via at most k edge deletions? We determine the computational complexity of this and related problems for different values of d. (C) 2021 Elsevier B.V. All rights reserved.
With the rapid growth of Internet, plenty of applications has been implemented for users to exchange resources with each other over networks. As a result, it has been a critical challenge to efficiently and fairly all...
详细信息
With the rapid growth of Internet, plenty of applications has been implemented for users to exchange resources with each other over networks. As a result, it has been a critical challenge to efficiently and fairly allocate resource among participating agents. Motivated by the famous BitTorrent system, a BD Mechanism for resource exchange allocation is proposed, which is based on a combinatorial structure called bottleneck decomposition. The mechanism has been shown to lead to market equilibrium [1], a state optimizing each individual's utility, and to be truthful [2], [3], that is robust against agents' strategic behaviors. However, the crux on how to compute a bottleneck decomposition of any graph remains untouched. In this article, we focus on the computation of bottleneck decomposition to fill the blanks and prove that the bottleneck decomposition of a network can be computed in $O(n<^>6\,\log (nU))$O(n6log(nU)) time, where $n$n and $U$U are the number of agents and the maximal amount of resource any agent has in the network. Based on the bottleneck decomposition, a fair allocation in a resource exchange network can be obtained in polynomial time. We further carefully discuss the fairness in resource exchange scenario, showing the derived allocation satisfies several common fairness notions simultaneously.
The goal of this paper is to explore and to provide tools for the investigation of the problems of unit-length scheduling of incompatible jobs on uniform machines. We present two new algorithms that are a significant ...
详细信息
The goal of this paper is to explore and to provide tools for the investigation of the problems of unit-length scheduling of incompatible jobs on uniform machines. We present two new algorithms that are a significant improvement over the known algorithms. The first one is algorithm 2 which is 2-approximate for the problem Qm vertical bar p(j) =1,G = bisubquartic vertical bar C-max. The second one is algorithm 3 which is 4-approximate for the problem Qm vertical bar p(j) =1,G = bisubquarticl vertical bar Sigma C-j, where m is an element of {2, 3, 4). The theory behind the proposed algorithms is based on the properties of 2-coloring with maximal coloring width, and on the properties of ideal machine, an abstract machine that we introduce in this paper.
This paper is concerned with algorithms and applications of decreasing minimization on an M-convex set, which is the set of integral elements of an integral base-polyhedron. Based on a recent characterization of decre...
详细信息
This paper is concerned with algorithms and applications of decreasing minimization on an M-convex set, which is the set of integral elements of an integral base-polyhedron. Based on a recent characterization of decreasingly minimal (dec-min) elements, we develop a strongly polynomial algorithm for computing a dec-min element of an M-convex set. The matroidal feature of the set of dec-min elements makes it possible to compute a minimum cost dec-min element, as well. Our second goal is to exhibit various applications in matroid and network optimization, resource allocation, and (hyper)graph orientation. We extend earlier results on semi-matchings to a large degree by developing a structural description of dec-min in-degree bounded orientations of a graph. This characterization gives rise to a strongly polynomial algorithm for finding a minimum edge-cost dec-min orientation.
Fault-tolerant networks are often modeled as s-hamiltonian graphs. Thus it is of interests to find graph families in which whether a graph is s-hamiltonian can be determined in polynomial time. An hourglass is a graph...
详细信息
Fault-tolerant networks are often modeled as s-hamiltonian graphs. Thus it is of interests to find graph families in which whether a graph is s-hamiltonian can be determined in polynomial time. An hourglass is a graph obtained from K-5 by deleting the edges in a cycle of length 4, and an hourglass-free graph is one that has no induced subgraph isomorphic to an hourglass. Kriesell in [J. Combin. Theory Ser. B, 82 (2001), 306-315] proved that every 4 connected hourglass-free line graph is Hamilton-connected, and Kaiser, Ryjacek and Vrana in [Discrete Mathematics, 321 (2014) 1-11] extended it by showing that every 4-connected hourglass-free line graph is 1-Hamilton-connected. We characterize all essentially 4-edge connected graphs whose line graph is hourglass-free. Consequently we prove that for any integer s and for any hourglass-free line graph L(G), each of the following holds. (i) Ifs >= 2, then L(G) is s-hamiltonian if and only if kappa(L(G)) >= s + 2;(ii) Ifs >= 1, then L(G) is s-Hamilton-connected if and only if kappa(L(G)) >= s + 3. (c) 2022 Published by Elsevier B.V.
This paper proposes an arc-search interior-point algorithm for convex quadratic programming with box constraints. The problem has many applications, such as optimal control with actuator saturation. It is shown that a...
详细信息
This paper proposes an arc-search interior-point algorithm for convex quadratic programming with box constraints. The problem has many applications, such as optimal control with actuator saturation. It is shown that an explicit feasible starting point exists for this problem. Therefore, an efficient feasible interior-point algorithm is proposed to tackle the problem. It is proved that the proposed algorithm is polynomial and has the best known complexity bound O (root nlog(1/is an element of). Moreover, the search neighborhood for this special problem is wider than an algorithm for general convex quadratic programming problems, which implies that longer steps and faster convergence are expected. Finally, an engineering design problem is considered and the algorithm is applied to solve the engineering problem.
暂无评论