We describe a new algorithm for generating all maximal bicliques (i.e. complete bipartite. not necessarily induced subgraphs) of a graph. The algorithm is inspired by, and is quite similar to. the consensus method use...
详细信息
We describe a new algorithm for generating all maximal bicliques (i.e. complete bipartite. not necessarily induced subgraphs) of a graph. The algorithm is inspired by, and is quite similar to. the consensus method used in propositional logic. We show that some variants of the algorithm are totally polynomial, and even incrementally polynomial. The total complexity of the most efficient variant of the algorithms presented here is polynomial in the input size. and only linear in the output size. Computational experiments demonstrate its high efficiency on randomly generated graphs with up to 2000 vertices and 20,000 edges. (C) 2003 Elsevier B.V. All rights reserved.
The vertex connectivity of an m-edge n-vertex undirected graph is the smallest number of vertices whose removal disconnects the graph, or leaves only a singleton vertex. In this paper, we give a reduction from the ver...
详细信息
ISBN:
(纸本)9781450380539
The vertex connectivity of an m-edge n-vertex undirected graph is the smallest number of vertices whose removal disconnects the graph, or leaves only a singleton vertex. In this paper, we give a reduction from the vertex connectivity problem to a set of maxflow instances. Using this reduction, we can solve vertex connectivity in (O) over tilde (m(alpha)) time for any alpha >= 1, if there is a m(alpha)-time maxflow algorithm. Using the current best maxflow algorithm that runs in m(4/3+o(1)) time (Kathuria, Liu and Sidford, FOCS 2020), this yields a m(4/3+o(1) )- time vertex connectivity algorithm. This is the first improvement in the running time of the vertex connectivity problem in over 20 years, the previous best being an (O) over tilde (mn)-time algorithm due to Henzinger, Rao, and Gabow (FOCS 1996). Indeed, no algorithm with an o(mn) running time was known before our work, even if we assume an (O) over tilde (m)-time maxflow algorithm. Our new technique is robust enough to also improve the best (O) over tilde (mn)-time bound for directed vertex connectivity to mn(1-1/12+o(1)) time.
Ptolemaic graphs are graphs that satisfy the Ptolemaic inequality for any four vertices. The graph class coincides with the intersection of chordal graphs and distance hereditary graphs, and it is a natural generaliza...
详细信息
ISBN:
(纸本)3540309357
Ptolemaic graphs are graphs that satisfy the Ptolemaic inequality for any four vertices. The graph class coincides with the intersection of chordal graphs and distance hereditary graphs, and it is a natural generalization of block graphs (and hence trees). In this paper, a new characterization of ptolemaic graphs is presented. It is a laminar structure of cliques, and leads us to a canonical tree representation, which gives a simple intersection model for ptolemaic graphs. The tree representation is constructed in linear time from a perfect elimination ordering obtained by the lexicographic breadth first search. Hence the recognition and the graph isomorphism for ptolemaic graphs can be solved in linear time. Using the tree representation, we also give an O(n) time algorithm for the Hamiltonian cycle problem.
An independent set in a graph G is a collection of vertices with no edge between any two. The Independent Set problem is a classic NP-Hard problem that takes in a graph G and the task is to find an independent set in ...
详细信息
An independent set in a graph G is a collection of vertices with no edge between any two. The Independent Set problem is a classic NP-Hard problem that takes in a graph G and the task is to find an independent set in G of maximum size. An induced subgraph of G is another graph, H, where the vertex set of H is a subset V (H) ⊆ V (G), and the edge set of H is all edges uv in E(G) where u, v ∈ V (H). A graph is said to be H-free if it does not contain H as an induced subgraph. Lastly, quasi-polynomial functions are functions that grow (slightly) faster than polynomial functions by allowing poly-log terms in their exponents, for example, n log2(n) is a quasi-polynomial function. In this thesis, we will provide a quasi-polynomial time algorithm for Independent Set on Pk-free graphs, where Pk denotes a path with k vertices. We will later extend this result in multiple ways. First, we give a quasi-polynomial time algorithm for Independent Set as well as related problems, such as Feedback Vertex Set on C>k-free graphs, which are graphs that do not contain induced cycles with more than k vertices. Additionally, we will give a quasi-polynomial time algorithm for Independent Set on H-free graphs where H is a forest of paths and subdivided claws. A subdivided claw is a graph formed by taking three paths of any desired length along with a vertex v that is a neighbor of exactly one end vertex in each of the three paths. This last result resolves an open problem first investigated by Alekseev in *** a seemingly different research thread, we will characterize graph classes with few minimal separators. A minimal separator is a set S such that there are two vertices u, v in different components of G − S and for any proper subset S ′ ⊂ S, u and v are in the same component of G − S ′ . A class F of graphs is called tame if every graph in F on n vertices contains at most n O(1) minimal separators, quasi-tame if every graph in F on n vertices contains at mostn logO(1)(n) minimal sepa
The generation of constitutional isomer chemical spaces has been a subject of cheminformatics since the early 1960s, with applications in structure elucidation and elsewhere. In order to perform such a generation effi...
详细信息
The generation of constitutional isomer chemical spaces has been a subject of cheminformatics since the early 1960s, with applications in structure elucidation and elsewhere. In order to perform such a generation efficiently, exhaustively and isomorphism-free, the structure generator needs to ensure the building of canonical graphs already during the generation step and not by subsequent filtering. Here we present MAYGEN, an open-source, pure-Java development of a constitutional isomer molecular generator. The principles of MAYGEN's architecture and algorithm are outlined and the software is benchmarked in single-threaded mode against the state-of-the-art, but closed-source solution MOLGEN, as well as against the best open-source solution PMG. Based on the benchmarking, MAYGEN is on average 47 times faster than PMG and on average three times slower than MOLGEN in performance.
The SURJECTIVE H-COLOURING problem is to test if a given graph allows a vertex-SURJECTIVE homomorphism to a fixed graph H. The complexity of this problem has been well studied for undirected (partially) reflexive grap...
详细信息
The SURJECTIVE H-COLOURING problem is to test if a given graph allows a vertex-SURJECTIVE homomorphism to a fixed graph H. The complexity of this problem has been well studied for undirected (partially) reflexive graphs. We introduce endo-triviality, the property of a structure that all of its endomorphisms that do not have range of size 1 are automorphisms, as a means to obtain complexity-theoretic classifications of SURJECTIVE H-COLOURING in the case of reflexive digraphs. Chen (2014) proved, in the setting of constraint satisfaction problems, that SURJECTIVE H-COLOURING is NP-complete if H has the property that all of its polymorphisms are essentially unary. We give the first concrete application of his result by showing that every endo-trivial reflexive digraph H has this property. We then use the concept of endo-triviality to prove, as our main result, a dichotomy for SURJECTIVE H-COLOURING when H is a reflexive tournament: if H is transitive, then SURJECTIVE H-COLOURING is in NL;otherwise, it is NP-complete. By combining this result with some known and new results, we obtain a complexity classification for SURJECTIVE H-COLOURING when H is a partially reflexive digraph of size at most 3.
Experiments on a large set of real-world public transport networks are also included, helping to illustrate the performance of these methods.In the second article, Thiruvady, Blum and Ernst use a resource constrained ...
详细信息
Experiments on a large set of real-world public transport networks are also included, helping to illustrate the performance of these methods.
In the second article, Thiruvady, Blum and Ernst use a resource constrained job scheduling problem to help test a variety of different hybrid algorithms that combine elements of heuristics and mathematical programming [2].
[...]they develop a multiobjective beam search and ant colony optimisation hybrid that uses problem-specific bounds to help guide the search towards feasibility.
The maximum clique problem (MCP) is an old NP-complete problem which has been frequently used for delivering the NP-completeness of many other problems with respect to computational complexity literature. In this pape...
详细信息
The maximum clique problem (MCP) is an old NP-complete problem which has been frequently used for delivering the NP-completeness of many other problems with respect to computational complexity literature. In this paper, we give a heuristic based genetic algorithm for solving this problem. By incorporating a heuristic into the crossover operator, we speed up the convergence rate of our algorithm - GACP (genetic algorithm for clique problem). GACP has been tested on a variety of challenging benchmarks including DIMACS instances and compared with two recently efficient algorithms. Experimental results show that GACP not only competes consistently with these algorithms but also performed well at solving the maximum clique problem.
graph canonization is the problem of computing a unique representative, a canon, from the isomorphism class of a given graph. This implies that two graphs are isomorphic exactly if their canons are equal. We show that...
详细信息
graph canonization is the problem of computing a unique representative, a canon, from the isomorphism class of a given graph. This implies that two graphs are isomorphic exactly if their canons are equal. We show that graphs of bounded tree width can be canonized by logarithmic-space (logspace) algorithms. This implies that the isomorphism problem for graphs of bounded tree width can be decided in logspace. In the light of isomorphism for trees being hard for the complexity class logspace, this makes the ubiquitous class of graphs of bounded tree width one of the few classes of graphs for which the complexity of the isomorphism problem has been exactly determined.
暂无评论