Observable graphs

An edge-colored directed graph is observable if an agent that moves along its edges from node to node is able to determine his position in the graph after a sufficiently long observation of the edge colors, and without accessing any information about the traversed nodes. When the agent is able to determine his position only from time to time, the graph is said to be partly observable. Observability in graphs is desirable in situations where autonomous agents are moving on a network and they want to localize themselves with limited information. In this paper, we completely characterize observable and partly observable graphs and show how these concepts relate to other concepts in the literature. Based on these characterizations, we provide polynomial time algorithms to decide observability, to decide partial observability, and to compute the minimal number of observations necessary for finding the position of an agent. In particular we prove that in the worst case this minimal number of observations increases quadratically with the number of nodes in the graph. We then consider the more difficult question of assigning colors to a graph so as to make it observable and we prove that two different versions of this problem are NP-complete.     

Generating the maximum spanning trees of a weighted graph

The present paper contains an efficient algorithm for generating all the maximum spanning trees of a weighted graph and a polynomial time algorithm for counting them. As known, the tree representations of an acylic hypergraph are exactly the maximum spanning trees of the weighted intersection graph of its edges. Therefore, they can be generated and counted by these algorithms.     

Partial inverse maximum spanning tree in which weight can only be decreased under $$l_p$$-norm

The maximum or minimum spanning tree problem is a classical combinatorial optimization problem. In this paper, we consider the partial inverse maximum spanning tree problem in which the weight function can only be decreased. Given a graph, an acyclic edge set, and an edge weight function, the goal of this problem is to decrease weights as little as possible such that there exists with respect to function containing the given edge set. If the given edge set has at least two edges, we show that this problem is APX-Hard. If the given edge set contains only one edge, we present a polynomial time algorithm.     

Edge searching weighted graphs

In traditional edge searching one tries to clean all of the edges in a graph employing the least number of searchers. It is assumed that each edge of the graph initially has a weight equal to one. In this paper we modify the problem and introduce the Weighted Edge Searching Problem by considering graphs with arbitrary positive integer weights assigned to its edges. We give bounds on the weighted search number in terms of related graph parameters including pathwidth. We characterize the graphs for which two searchers are sufficient to clear all edges. We show that for every weighted graph the minimum number of searchers needed for a not-necessarily-monotonic weighted edge search strategy is enough for a monotonic weighted edge search strategy, where each edge is cleaned only once. This result proves the NP-completeness of the problem.     

The Ehrhart Polynomial of the Birkhoff Polytope

The nth Birkhoff polytope is the set of all doubly stochastic n × n matrices, that is, those matrices with nonnegative real coefficients in which every row and column sums to one. A wide open problem concerns the volumes of these polytopes, which have been known for n $\leq$ 8. We present a new, complex-analytic way to compute the Ehrhart polynomial of the Birkhoff polytope, that is, the function counting the integer points in the dilated polytope. One reason to be interested in this counting function is that the leading term of the Ehrhart polynomial is—up to a trivial factor—the volume of the polytope. We implemented our methods in the form of a computer program, which yielded the Ehrhart polynomial (and hence the volume) of the ninth Birkhoff polytope, as well as the volume of the tenth Birkhoff polytope.     

How Many Needles are in a Haystack, or How to Solve #P-Complete Counting Problems Fast

We present two randomized entropy-based algorithms for approximating quite general #P-complete counting problems, like the number of Hamiltonian cycles in a graph, the permanent, the number of self-avoiding walks and the satisfiability problem. In our algorithms we first cast the underlying counting problem into an associate rare-event probability estimation, and then apply dynamic importance sampling (IS) to estimate efficiently the desired counting quantity. We construct the IS distribution by using two different approaches: one based on the cross-entropy (CE) method and the other one on the stochastic version of the well known minimum entropy (MinxEnt) method. We also establish convergence of our algorithms and confidence intervals for some special settings and present supportive numerical results, which strongly suggest that both ones (CE and MinxEnt) have polynomial running time in the size of the problem.     

Vertex insertion approximates the crossing number of apex graphs

An apex graph is a graph G from which only one vertex v has to be removed to make it planar. We show that the crossing number of such G can be approximated up to a factor of Δ(G−v)⋅d(v)/2 by solving the vertex inserting problem, i.e. inserting a vertex plus incident edges into an optimally chosen planar embedding of a planar graph. Since the latter problem can be solved in polynomial time, this establishes the first polynomial fixed-factor approximation algorithm for the crossing number problem of apex graphs with bounded degree.Furthermore, we extend this result by showing that the optimal solution for inserting multiple edges or vertices into a planar graph also approximates the crossing number of the resulting graph.     

Counterexamples to a conjecture by Gross,Mansour and Tucker on partial-dual genus polynomials of ribbon graphs

Gross, Mansour and Tucker introduced the partial-dual orientable genus polynomial and the partial-dual Euler genus polynomial. They computed these two partial-dual genus polynomials of four families of ribbon graphs, posed some research problems and made some conjectures. In this paper, we introduce the notion of signed interlace sequences of bouquets and obtain the partial-dual Euler genus polynomials for all ribbon graphs with the number of edges less than 4 and the partial-dual orientable genus polynomials for all orientable ribbon graphs with the number of edges less than 5 in terms of signed interlace sequences. We check all the conjectures and find a counterexample to the Conjecture 3.1 in their paper: There is no orientable ribbon graph having a non-constant partial-dual genus polynomial with only one non-zero coefficient. Motivated by this counterexample, we further find an infinite family of counterexamples to the conjecture.     

A Solution to the Generalized Cevian Problem Using Forest Polynomials

In this paper, we examine the effect of dissecting an n-dimensional simplex using cevians (cross-sections passing through n−1 of the vertices of the simplex). We describe a formula for the number of pieces the simplex is dissected into using a polynomial involving only the number of each type of cevian. The polynomial in question involves terms involving the edges of the simplex, but discarding those terms involving cycles of the underlying graph. Thus, we call such a polynomial a “forest polynomial.”     

关于图的直径和平均距离

图的直径和平均距离是度量网络有效性的两个重要参数．Ore通过图的顶点数和直径给出无向图的最大边数．Entringer，Jakson，Slater和Ng，Teh通过图的顶点数和边数分别给出无向图和有向图平均距离的下界．该文提供这两个结果的简单证明，给出有向图类似Ore的结果，并通过图的直径改进Entringer等人的结果到更一般的情形．结合本文和Ore的结果，可以得到一个无向图和有向图平均距离的下界，它比Plesnik得到的下界更好．     

Approximation algorithms for solving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2

The problem of finding two disjoint Hamiltonian cycles of minimum sum weight is considered in a complete undirected graph with arbitrarily chosen weights of the edges 1 and 2. The main result of the paper is the presentation of polynomial algorithms with the currently best guaranteed performance factors 26/21 and 6/5. These algorithms are based on finding the partial tours with a large number of edges in the graphs of a special type.     

Weyl asymptotics of bisingular operators and Dirichlet divisor problem

We consider a class of pseudodifferential operators, with crossed vector valued symbols, defined on the product of two closed manifolds. We study the asymptotic expansion of the counting function of positive selfadjoint operators in this class. Using a general Theorem of Aramaki, we can determine the first term of the asymptotic expansion of the counting function and, in a special case, we are able to find the second term. We give also some examples, emphasizing connections with problems of analytic number theory, in particular with Dirichlet divisor function.     

Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm

Hamiltonian Path/Cycle are well known NP-complete problems on general graphs, but their complexity status for permutation graphs has been an open question in algorithmic graph theory for many years. In this paper, we prove that theHamiltonian Path problem is solvable in polynomial time even for the larger class of cocomparability graphs. Our result is based on a nice relationship between Hamiltonian paths and the bump number of partial orders. As another consequence we get a new interpretation of the bump number in terms of path partitions, leading to polynomial time solutions of theHamiltonian Path/Cycle Completion problems in cocomparability graphs.This research was supported in part by ONR for third author and by NSERC under grant number A1798 for fourth author.     

Packing subgraphs in a graph

We show that the problem of packing edges and triangles in a graph in order to cover the maximum number of nodes can be solved in polynomial time. More generally we present results for the problem of packing edges and a family of hypomatchable subgraphs.     

Shortest Paths with Shortest Detours

This paper is concerned with a biobjective routing problem, called the shortest path with shortest detour problem, in which the length of a route is minimized as one criterion and, as second, the maximal length of a detour route if the chosen route is blocked is minimized. Furthermore, the relation to robust optimization is pointed out, and we present a new polynomial time algorithm, which computes a minimal complete set of efficient paths for the shortest path with shortest detour problem. Moreover, we show that the number of nondominated points is bounded by the number of arcs in the graph.     

On the minimum corridor connection problem and other generalized geometric problems

In this paper we discuss the complexity and approximability of the minimum corridor connection problem where, given a rectilinear decomposition of a rectilinear polygon into “rooms”, one has to find the minimum length tree along the edges of the decomposition such that every room is incident to a vertex of the tree. We show that the problem is strongly NP-hard and give a subexponential time exact algorithm. For the special case when the room connectivity graph is k-outerplanar the algorithm running time becomes cubic. We develop a polynomial time approximation scheme for the case when all rooms are fat and have nearly the same size. When rooms are fat but are of varying size we give a polynomial time constant factor approximation algorithm.     

Vertex partitions of r-edge-colored graphs

Let G be an edge-colored graph.The monochromatic tree partition problem is to find the minimum number of vertex disjoint monochromatic trees to cover the all vertices of G.In the authors' previous work,it has been proved that the problem is NP-complete and there does not exist any constant factor approximation algorithm for it unless P=NP.In this paper the authors show that for any fixed integer r≥5,if the edges of a graph G are colored by r colors,called an r-edge-colored graph,the problem remains NP-complete.Similar result holds for the monochromatic path(cycle)partition problem.Therefore,to find some classes of interesting graphs for which the problem can be solved in polynomial time seems interesting. A linear time algorithm for the monochromatic path partition problem for edge-colored trees is given.     

On Four-Connecting a Triconnected Graph

We consider the problem of finding a smallest set of edges whose addition four-connects a triconnected graph. This is a fundamental graph-theoretic problem that has applications in designing reliable networks and improving statistical database security. We present an O(n · α(m, n) + m)-time algorithm for four-connecting an undirected graph G that is triconnected by adding the smallest number of edges, where n and m are the number of vertices and edges in G, respectively, and α(m, n) is the inverse Ackermann function. This is the first polynomial time algorithm to solve this problem exactly.In deriving our algorithm, we present a new lower bound for the number of edges needed to four-connect a triconnected graph. The form of this lower bound is different from the form of the lower bound known for biconnectivity augmentation and triconnectivity augmentation. Our new lower bound applies for arbitrary k and gives a tighter lower bound than the one known earlier for the number of edges needed to k-connect a (k − 1)-connected graph. For k = 4, we show that this lower bound is tight by giving an efficient algorithm to find a set of edges whose size equals the new lower bound and whose addition four-connects the input triconnected graph.     

Implementation of parallel branch-and-bound algorithms – experiences with the graph partitioning problem

Parallel processing is one of the essential concepts in the attempts to increase the computational power available for solving continuous and discrete optimization problems. In the case where an optimization algorithm is search-based, crucial issues of parallel distributed implementations are work-load distribution and granularity, i.e. how to distribute the search space among processors and how to control the amount of processing between interprocessor communication. The present paper compares distributed implementations of two branch-and-bound algorithms for the graph partitioning problem: Given an undirected graph with an even number of edges and weights assigned to each edge, partition the vertices into two subsets of equal size such that the sum of the costs of edges connecting vertices in different subsets is as small as possible. The problem is known to be NP-complete. The two branch-and-bound methods compared differ in design strategy: One is based on time-consuming bound calculations leading to tight bounds and thus a narrow search tree with few nodes, whereas the other employs an easy bound calculation scheme leading to a larger search tree. Both have been implemented on an iPSC-hypercube with 32 processors. We investigate the influence of the design strategy on the performance of the algorithms.     

多项式方程组的主项解耦消元法

本文提出多项式组符号求解的主项解耦 (主项只含主元 )消元法 :视多项式为变元不同幂积的线性组合 ,以主项解耦三角型多项式组 DTS为引导 ,用逐项伪除求余式 ,将多项式组 PS化为与其同解的 DTS.内容涉及 :消元算法、DTS的存在性与结构特性、零点集结构公式等 .亦对 Grobner基法、吴文俊消元法与本文方法之间的相互联系、区别以及特点进行了比较 .研究表明主项解耦消元法适用于一般多项式组且效率较高