An Algorithm To Recognize A Generalized Line Graph And Output It's Root Graph
An algorithmic Friedman-Pippenger theorem on tree embeddings and applications.
An alternative construction of normal numbers
A new class of -adic normal numbers is built recursively by using Eulerian paths in a sequence of de Bruijn digraphs. In this recursion, a path is constructed as an extension of the previous one, in such way that the -adic block determined by the path contains the maximal number of different -adic subblocks of consecutive lengths in the most compact arrangement. Any source of redundancy is avoided at every step. Our recursive construction is an alternative to the several well-known concatenative...
An approximation algorithm for the total covering problem
We introduce a 2-factor approximation algorithm for the minimum total covering number problem.
An attractive class of bipartite graphs
In this paper we propose a structural characterization for a class of bipartite graphs defined by two forbidden induced subgraphs. We show that the obtained characterization leads to polynomial-time algorithms for several problems that are NP-hard in general bipartite graphs.
An efficient algorithm for the transversal hypergraph generation.
An efficient -centroid location algorithm for cographs.
An evolutionary formulation of the crossing number problem.
An exact performance bound for an time greedy matching procedure.
Approximating clustering coefficient and transitivity.
Approximation algorithms for some graph partitioning problems.
Approximation algorithms for the traveling salesman problem with range condition
Approximation Algorithms for the Traveling Salesman Problem with Range Condition
We prove that the Christofides algorithm gives a approximation ratio for the special case of traveling salesman problem (TSP) in which the maximum weight in the given graph is at most twice the minimum weight for the odd degree restricted graphs. A graph is odd degree restricted if the number of odd degree vertices in any minimum spanning tree of the given graph is less than times the number of vertices in the graph. We prove that the Christofides algorithm is more efficient (in terms...
Approximations of weighted independent set and hereditary subset problems.
Arbology: Trees and pushdown automata
We present a unified and systematic approach to basic principles of Arbology, a new algorithmic discipline focusing on algorithms on trees. Stringology, a highly developed algorithmic discipline in the area of string processing, can use finite automata as its basic model of computation. For various kinds of linear notations of ranked and unranked ordered trees it holds that subtrees of a tree in a linear notation are substrings of the tree in the linear notation. Arbology uses pushdown automata...
Area Requirement and Symmetry Display of Planar Upward Drawings.
Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number
We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph G = (V,E) and a spanning subgraph H of G (the backbone of G), a λ-backbone coloring for G and H is a proper vertex coloring V→ {1,2,...} of G in which the colors assigned to adjacent vertices in H differ by at least λ. The algorithmic and combinatorial properties of backbone colorings have been studied for various types of backbones in a number of papers. The main outcome...
Balanced problems on graphs with categorization of edges
Suppose a graph G = (V,E) with edge weights w(e) and edges partitioned into disjoint categories S₁,...,Sₚ is given. We consider optimization problems on G defined by a family of feasible sets (G) and the following objective function: For an arbitrary number of categories we show that the L₅-perfect matching, L₅-a-b path, L₅-spanning tree problems and L₅-Hamilton cycle (on a Halin graph) problem are NP-complete. We also summarize polynomiality results concerning above objective functions for arbitrary...
Block decomposition approach to compute a minimum geodetic set
In this paper, we develop a divide-and-conquer approach, called block decomposition, to solve the minimum geodetic set problem. This provides us with a unified approach for all graphs admitting blocks for which the problem of finding a minimum geodetic set containing a given set of vertices (g-extension problem) can be efficiently solved. Our method allows us to derive linear time algorithms for the minimum geodetic set problem in (a proper superclass of) block-cacti and monopolar chordal graphs....
Bootstrap clustering for graph partitioning
Given a simple undirected weighted or unweighted graph, we try to cluster the vertex set into communities and also to quantify the robustness of these clusters. For that task, we propose a new method, called bootstrap clustering which consists in (i) defining a new clustering algorithm for graphs, (ii) building a set of graphs similar to the initial one, (iii) applying the clustering method to each of them, making a profile (set) of partitions, (iv) computing a consensus partition for this profile,...