Search

A graph G = ( V , E ) is a word-representable graph if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if ( x , y ) ∈ E for each x ≠ y . In this paper we give an effective characterization of word-representable graphs in terms of orientations. Namely, we show that a graph is word-representable if and only if it admits a semi-transitive orientation defined in the paper. This allows us to prove a number of results about word-representable graphs, in particular showing that the recognition problem is in NP, and that word-representable graphs include all 3-colorable graphs. We also explore bounds on the size of the word representing the graph. The representation number of G is the minimum k such that G is a representable by a word, where each letter occurs k times; such a k exists for any word-representable graph. We show that the representation number of a word-representable graph on n vertices is at most 2 n , while there exist graphs for which it is n / 2 . [ABSTRACT FROM AUTHOR]

This paper introduces the notion of involution module, the first generalization of the modular decomposition of 2-structures which has a unique linear-sized decomposition tree. We derive an O ( n 2 ) decomposition algorithm and we take advantage of the involution modular decomposition tree to obtain several algorithmic results. It is well-known that cographs (or equivalently P 4 -free graphs) are the graphs that are totally decomposable w.r.t modular decomposition. In a similar way, we introduce the class of switch cographs, as the class of graphs that are totally decomposable w.r.t involution modular decomposition. This class generalizes the class of cographs and appears to be exactly the class of (Bull, Gem, Co-Gem, C 5 )-free graphs. We use our new decomposition tool to design three practical algorithms for the maximum cut, vertex cover and vertex separator problems. The complexity of these problems was still unknown for this class of graphs. This paper also improves the complexity of the maximum clique, the maximum independent set, the chromatic number and the maximum clique cover problems by giving efficient algorithms, thanks to the decomposition tree. Eventually, we show that this class of graphs has clique-width at most 4 and that a clique-width expression can be computed in linear time. [ABSTRACT FROM AUTHOR]

By resorting to a new matrix product, called semi-tensor product of matrices, this paper investigates the minimum stable set and core of graph, and also presents a number of results and algorithms. By defining a characteristic logical vector and using matrix expressions of logical functions, a new algebraic representation is derived for the externally stable set. Then, based on the algebraic representation, an algorithm is established to find all the externally stable sets. According to this algorithm, a new necessary and sufficient condition is obtained to determine whether a given vertex subset is an absolutely minimum externally stable set or not. Meanwhile, a new algorithm is also obtained to find all the absolutely minimum externally stable sets. Finally, the graph core, which is simultaneously externally stable set and internally stable set, is investigated. Here the internally stable set requires that internal nodes of this set are all disconnected with each other. Using semi-tensor product, some necessary and sufficient conditions are presented, and then an algorithm is established to find all the graph cores. The study of illustrative examples shows that the results/algorithms presented in this paper are effective. [ABSTRACT FROM AUTHOR]

We study the problem of finding in a graph an inclusionwise maximal independent set of minimum cardinality, known as minimum maximal independent set or independent dominating set problem. This is one of the hardest problems in algorithmic graph theory. In particular, restricted to the class of so called SAT-graphs, this problem coincides with satisfiability , the central problem of theoretical computer science. The class of SAT-graphs, and many other important graph classes, such as graphs of bounded vertex degree or line graphs, can be characterized by finitely many forbidden induced subgraphs. We call such classes finitely defined. The paper [R. Boliac and V. Lozin, Independent domination in finitely defined classes of graphs, Theoretical Computer Science, 301 (2003) 271–284] reveals various conditions under which the independent dominating set problem remains NP-hard in a finitely defined class. In the present paper, we identify a number of finitely defined classes where the problem admits polynomial-time solutions. In particular, we prove that the problem is solvable in polynomial time in the class of P 2 + P 3 -free graphs by correcting a mistake of the first two authors of the paper in their earlier solution. This result is in a sharp contrast with the fact that in the class of P 3 + P 3 -free graphs the problem is known to be NP-hard, since this class contains all SAT-graphs. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study the geodetic convexity of graphs, focusing on the problem of the complexity of computing a minimum hull set of a graph in several graph classes. For any two vertices of a connected graph , the closed interval of and is the set of vertices that belong to some shortest -path. For any , let . A subset is geodesically convex or convex if . In other words, a subset is convex if, for any and for any shortest -path , . Given a subset , the convex hull of is the smallest convex set that contains . We say that is a hull set of if . The size of a minimum hull set of is the hull number of , denoted by . The Hull Number problem is to decide whether , for a given graph and an integer . Dourado et al. showed that this problem is NP-complete in general graphs. In this paper, we answer an open question of Dourado et al. (2009) [1] by showing that the Hull Number problem is NP-hard even when restricted to the class of bipartite graphs. Then, we design polynomial-time algorithms to solve the Hull Number problem in several graph classes. First, we deal with the class of complements of bipartite graphs. Then, we generalize some results in Araujo et al. (2011) [2] to the class of -graphs and to cacti. Finally, we prove tight upper bounds on the hull numbers. In particular, we show that the hull number of an -node graph without simplicial vertices is at most in general, at most if is regular or has no triangle, and at most if has girth at least . [Copyright &y& Elsevier]

Abstract: In recent years, the use of extensible processors has been increased. Extensible processors extend the base instruction set of a general-purpose processor with a set of custom instructions. Custom instructions that can be implemented in special hardware units make it possible to improve performance and decrease power consumption in extensible processors. The key issue involved is to generate and select automatically the custom instructions from a high-level application code. In this paper, we propose a new efficient algorithm for the automatic generation of all candidate instructions (or patterns). Our pattern generation algorithm identify all feasible connected and disjoint patterns under different constraints. Compared to a previously proposed well-known algorithm, our algorithm solves the problem more efficiently by taking advantage of the topological property of data flow graph (DFG) as well as overcoming the drawbacks of the previously proposed algorithm. An extension of the proposed algorithm is also presented in this paper. The extended algorithm further radically reduce the search space by considering the input resolving nodes. Experimental results show that our algorithms can achieve orders of magnitude speedup over the well-know algorithm. [Copyright &y& Elsevier]

Abstract: Recently, there has been significant theoretical progress towards fixed-parameter algorithms for the DOMINATING SET problem of planar graphs. It is known that the problem on a planar graph with vertices and dominating number can be solved in time using tree/branch-decomposition based algorithms. In this paper, we report computational results of Fomin and Thilikos algorithm which uses the branch-decomposition based approach. The computational results show that the algorithm can solve the DOMINATING SET problem of large planar graphs in a practical time and memory space for the class of graphs with small branchwidth. For the class of graphs with large branchwidth, the size of instances that can be solved by the algorithm in practice is limited to about one thousand edges due to a memory space bottleneck. The practical performances of the algorithm coincide with the theoretical analysis of the algorithm. The results of this paper suggest that the branch-decomposition based algorithms can be practical for some applications on planar graphs. [Copyright &y& Elsevier]

The method of augmenting graphs is a general approach to solve the Maximum Independent Set problem. Our objective is to employ this approach to develop polynomial-time algorithms for some so-called Maximum Set problems, i.e. problems which can be stated as follows. Given a (simple) graph G , find a maximum vertex subset S of G such that the subgraph induced by S satisfies a given property Π . Such problems were shown to be NP-hard in general if the properties considered are non-trivial and hereditary Lewis and Yannakakis (1980) and Yannakakis (1978). In this paper, using the augmenting graph technique, we describe a graph class, in which some problems can be solved in polynomial time. We also prove the NP-hardness of some Maximum Set problems where the considered properties are not hereditary. [ABSTRACT FROM AUTHOR]

A many-to-many k -disjoint path cover ( k -DPC for short) of a graph G joining the pairwise disjoint vertex sets S and T , each of size k , is a collection of k vertex-disjoint paths between S and T , which altogether cover every vertex of G . This is classified as paired , if each vertex of S must be joined to a specific vertex of T , or unpaired , if there is no such constraint. In this paper, we develop a linear-time algorithm for the Unpaired DPC problem of finding an unpaired DPC joining S and T given in a unit interval graph, to which the One-to-One DPC and the One-to-Many DPC problems are reduced in linear time. Additionally, we show that the Paired k - DPC problem on a unit interval graph is polynomially solvable for any fixed k . [ABSTRACT FROM AUTHOR]

Diagnosability plays an important role in measuring the reliability of interconnection networks. Conditional faulty set is a special faulty set that does not contain all of neighbors of any vertex in a network. The conditional diagnosability is a metric that can give the maximum cardinality of the conditional faulty sets that the system is guaranteed to identify. This paper shows that the conditional diagnosability of the bubble-sort star graph B S n under the MM model is 6 n − 15 for n ≥ 6 and under the PMC model is 8 n − 21 for n ≥ 5 . [ABSTRACT FROM AUTHOR]

An orthogonal ray graph is an intersection graph of horizontal rays (closed half-lines) and vertical rays in the plane, which is introduced in connection with the defect-tolerant design of nano-circuits. An orthogonal ray graph is a 3-directional orthogonal ray graph if every vertical ray has the same direction. A 3-directional orthogonal ray graph is a 2-directional orthogonal ray graph if every horizontal ray has the same direction. The characterizations and the complexity of the recognition problem have been open for orthogonal ray graphs and 3-directional orthogonal ray graphs, while various characterizations with a quadratic-time recognition algorithm have been known for 2-directional orthogonal ray graphs. In this paper, we show several characterizations with a linear-time recognition algorithm for orthogonal ray trees by using the 2-directional orthogonal ray trees. We also show that a tree is a 3-directional orthogonal ray graph if and only if it is a 2-directional orthogonal ray graph. Moreover, we show some necessary conditions for orthogonal ray graphs and 3-directional orthogonal ray graphs. [ABSTRACT FROM AUTHOR]

Controllability of complex networks has been one of the attractive research areas for both network and control community, and has yielded many promising and significant results in minimum inputs and minimum driver vertices. However, few studies have been devoted to studying the minimum controlled vertex set through which control over the network with arbitrary structure can be achieved. In this paper, we prove that the minimum driver vertices driven by different inputs are not sufficient to ensure the full control of the network when the associated graph contains the inaccessible strongly connected component which has perfect matching and propose an algorithm to identify a minimum controlled vertex set for network with arbitrary structure using convenient graph and mathematical tools. And the simulation results show that the controllability of network is correlated to the number of inaccessible strongly connected components which have perfect matching and these results promote us to better understand the relationship between the network’s structural characteristics and its control. [ABSTRACT FROM AUTHOR]

We consider the problem of finding an integral (and fractional) packing of branchings in a capacitated digraph with root-set demands. Schrijver described an algorithm that returns a packing with at most m + n 3 + r branchings that makes at most m ( m + n 3 + r ) calls to an oracle that basically computes a minimum cut, where n is the number of vertices, m is the number of arcs and r is the number of root-sets of the input digraph. Leston-Rey and Wakabayashi described an algorithm that returns a packing with at most m + r − 1 branchings but makes a large number of oracle calls. In this work we provide an algorithm, inspired on ideas of Schrijver and in a paper of Gabow and Manu, that returns a packing with at most m + r − 1 branchings and makes at most ( m + r + 2 ) n oracle calls. Moreover, for the arborescence packing problem our algorithm provides a packing with at most m − n + 2 arborescences–thus improving the bound of m of Leston-Rey and Wakabayashi–and makes at most ( m − n + 5 ) n oracle calls. [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]

Multiplex is a set of graphs on the same vertex set, i.e. { G ( V , E 1 ) , … , G ( V , E m ) } . It is a type of generalized graph to model the multiple relationships in a system with parallel edges between vertices. An important application in Network Science is to capture community structures in multiplex as a way to modularize the system. This paper is a literature review and comparative analysis on the existing communities detection algorithms for multiplex. The conclusion is that many of the algorithms deviate in the concept of multi-relational communities and the wrong choice of algorithm can deviate one from his intended concept. [ABSTRACT FROM AUTHOR]

In the game of Kayles , two players select alternatingly a vertex from a given graph G , but may never choose a vertex that is adjacent or equal to an already chosen vertex. The last player that can select a vertex wins the game. In this paper, we give an exact algorithm to determine which player has a winning strategy in this game. To analyze the running time of the algorithm, we introduce the notion of a K-set: a nonempty set of vertices W ⊆ V is a K-set in a graph G = ( V , E ) , if G [ W ] is connected and there exists an independent set X such that W = V − N [ X ] . The running time of the algorithm is bounded by a polynomial factor times the number of K-sets in G . We prove that the number of K-sets in a graph with n vertices is bounded by O ( 1.6052 n ) . A computer-generated case analysis improves this bound to O ( 1.6031 n ) K-sets, and thus we have an upper bound of O ( 1.6031 n ) on the running time of the algorithm for Kayles . We also show that the number of K-sets in a tree is bounded by n ⋅ 3 n / 3 and thus Kayles can be solved on trees in O ( 1.4423 n ) time. We show that apart from a polynomial factor, the number of K-sets in a tree is sharp. As corollaries, we obtain that determining which player has a winning strategy in the games G avoid ( POS DNF 2 ) and G seek ( POSDNF 3 ) can also be determined in O ( 1.6031 n ) time. In G avoid ( POSDNF 2 ) , we have a positive formula F on n Boolean variables in Disjunctive Normal Form with two variables per clause. Initially, all variables are false, and players alternately set a variable from false to true; the first player that makes F true loses the game. The game G seek ( POSDNF 3 ) is similar, but now there are three variables per clause, and the first player that makes F true wins the game. [ABSTRACT FROM AUTHOR]

A subset S of vertices of a graph G is called a k -path vertex cover if every path of order k in G contains at least one vertex from S . The cardinality of a minimum k -path vertex cover is called the k -path vertex cover number of a graph G , denoted by ψ k ( G ) . It is known that the minimum k -path vertex cover problem ( k -PVCP) is NP-hard for all k ≥ 2 . In this paper we consider the weighted version of a k -PVCP ( k -WPVCP), in which vertices are given weights, and the problem is to find a minimum weight set in G such that the graph obtained by deleting this set from G has no P k . This problem was briefly introduced by Tu and Zhou (2011) but has not been studied to much extent. We give solutions and efficient algorithms for the k -WPVCP for some special classes of graphs. In particular, for complete graphs and cycles, and most importantly an algorithm that computes the k -path vertex cover number of a tree with time complexity O ( k ⋅ | V ( G ) | ) is presented. [ABSTRACT FROM AUTHOR]

Abstract: A graph is said to be a set graph if it admits an acyclic orientation that is also extensional, in the sense that the out-neighborhoods of its vertices are pairwise distinct. Equivalently, set graphs are the underlying graphs of digraph representations of hereditarily finite sets, where a set is hereditarily finite if it is finite and has only hereditarily finite sets as members. It is known that every connected -free (or claw-free) graph is a set graph, and that an extensional acyclic orientation of such a graph can be found in polynomial time. In this paper, we generalize this result in three different directions. First, we identify the largest hereditary class of graphs such that for every connected induced subgraph of , it holds that is a set graph if and only if it is claw-free. Second, we consider graphs in which no two distinct induced claws have equal or adjacent centers, and prove that in this class of graphs set graphs can be equivalently characterized in terms of a property related to successive vertex removal. Finally, we show that for every , connected -free graphs admit an acyclic orientation that is -extensional, in the sense that at most distinct vertices can have the same out-neighborhood. This also leads to a simple linear time algorithm for finding an extensional acyclic orientation of a given connected claw-free graph, thus improving over the previous algorithm. [Copyright &y& Elsevier]

Abstract: A subset of the vertex set of a graph is a secure dominating set of if is a dominating set of and if, for each vertex not in , there is a neighbouring vertex of in such that the swap set is again a dominating set of . The secure domination number of , denoted by , is the cardinality of a smallest secure dominating set of . A linear algorithm is proposed in this paper for finding a minimum secure dominating set and hence the value for a tree . The algorithm is based on a strategy of repeatedly pruning away pendent spiders of after having dominated them securely. [Copyright &y& Elsevier]

Abstract: A -cocoloring of a graph is a partition of the vertex set of into at most independent sets and at most cliques. It is known that determining the cochromatic number and the split chromatic number, which are respectively the minimum and the minimum such that is -cocolorable, is NP-hard problem. A -graph is a graph such that every subset of at most vertices induces at most distinct ’s. In 2011, Bravo et al. obtained a polynomial time algorithm to decide if a -graph is -cocolorable (Bravo et al., 2011). In this paper, we extend this result by obtaining polynomial time algorithms to decide the -cocolorability and to determine the cochromatic number and the split chromatic number for -graphs for every fixed and for graphs with bounded treewidth. We also obtain a polynomial time algorithm to obtain the maximum -cocolorable subgraph of a -graph for every fixed . All these algorithms are fixed parameter tractable. [Copyright &y& Elsevier]

Abstract: We consider a frequency allocation problem, in which we are given a cellular telephone network whose geographical coverage area is divided into cells in which phone calls are serviced by frequencies assigned to them, so that none of the pairs of calls emanating from the same or neighboring cells is assigned the same frequency. The problem is to use the frequencies efficiently, i.e., to minimize the span of frequencies used. The frequency allocation problem can be regarded as a multicoloring problem on a weighted hexagonal graph. In this paper, we present a 1-local 4/3-competitive distributed algorithm for multicoloring a hexagonal graph without certain forbidden configuration (introduced in Šparl and Žerovnik (2010) [7]). [Copyright &y& Elsevier]

Abstract: In this paper, we study the online tree node assignment problem, which is a generalization of the well studied OVSF code assignment problem. Assigned nodes in a complete binary tree must follow the rule that each leaf-to-root path must contain at most one assigned node. At times, it is necessary to swap assigned nodes with unassigned nodes in order to accommodate some new node assignment. The target of this problem is to minimize the number of swaps in satisfying a sequence of node assignments and releases. This problem is fundamental, not only to the OVSF code assignment, but also to other applications, such as buddy memory allocation and hypercube subcube allocation. All the previous solutions to this problem are based on a sorted and compact configuration by assigning the nodes linearly and level by level, ignoring the intrinsic tree property in their assignments. Our contributions are: (1) give the concept of safe assignment, which is proved to be unique for any fixed set of node-assignment requests; (2) an 8-competitive algorithm by holding the safe assignment; and (3) an improved 6-competitive variant of this algorithm. Our algorithms are simple and easy to implement and our contributions represent meaningful improvements over recent results. [Copyright &y& Elsevier]

Abstract: A global forcing set of a simple connected graph with a perfect matching is a set of edges such that no two different perfect matchings of coincide on it. The minimum size of global forcing sets of is called the global forcing number of . Došlić proved that the global forcing number of a cata-condensed hexagonal system is equal to the number of its hexagons. In this paper, we consider normal hexagonal systems. By giving a criterion to determine if two adjacent hexagons of normal hexagonal systems form a nice subgraph, we establish a sharp lower bound on the global forcing number of normal hexagonal systems. For a kind of normal hexagonal systems called “divisible hexagonal systems”, we get a formula for the global forcing number and obtain a linear algorithm for finding a minimum global forcing set. [Copyright &y& Elsevier]

Abstract: A graph is a unipolar graph if there exists a partition such that is a clique and induces the disjoint union of cliques. The complement-closed class of generalized split graphs contains those graphs such that either or the complement of is unipolar. Generalized split graphs are a large subclass of perfect graphs. In fact, it has been shown that almost all -free (and hence, almost all perfect graphs) are generalized split graphs. In this paper, we present a recognition algorithm for unipolar graphs that utilizes a minimal triangulation of the given graph, and produces a partition when one exists. Our algorithm has running time , where is the number of edges added in a minimal triangulation of the given graph. Generalized split graphs can be recognized via this algorithm in time. We give algorithms on unipolar graphs for finding a maximum independent set and a minimum clique cover in time, and for finding a maximum clique and a minimum proper coloring in time, when a unipolar partition is given. These algorithms yield algorithms for the four optimization problems on generalized split graphs that have the same worst-case time bounds. We also report that the perfect code problem is NP-complete for chordal unipolar graphs. [Copyright &y& Elsevier]

Abstract: Let be a graph with vertex set . A moplex of is both a clique and a module whose neighborhood is a minimal separator in or empty. A moplex ordering of is an ordered partition of for some integer into moplexes which are defined in the successive transitory elimination graphs, i.e., for , is a moplex of the graph induced by and induces a clique. In this paper we prove the terminal vertex by an execution of the lexicographical depth-first search (LexDFS for short) algorithm on belongs to a moplex whose vertices are numbered consecutively and further that the LexDFS algorithm on defines a moplex ordering of , which is similar to the result about the maximum cardinality search (MCS for short) algorithm on chordal graphs [J.R.S. Blair, B.W. Peyton, An introduction to chordal graphs and clique trees, IMA Volumes in Mathematics and its Applications, 56 (1993) pp. 1–30] and the result about the lexicographical breadth-first search (LexBFS for short) algorithm on general graphs [A. Berry, J.-P. Bordat, Separability generalizes Dirac’s theorem, Discrete Appl. Math., 84 (1998) 43–53]. As a corollary, we can obtain a simple algorithm on a chordal graph to generate all minimal separators and all maximal cliques. [Copyright &y& Elsevier]

Abstract: Let be a graph on vertices. We call a subset of the vertex set -small if, for every vertex , . A subset is called -large if, for every vertex , . Moreover, we denote by the minimum integer such that there is a partition of into -small sets, and by the minimum integer such that there is a partition of into -large sets. In this paper, we will show tight connections between -small sets, respectively -large sets, and the -independence number, the clique number and the chromatic number of a graph. We shall develop greedy algorithms to compute in linear time both and and prove various sharp inequalities concerning these parameters, which we will use to obtain refinements of the Caro–Wei Theorem, Turán’s Theorem and the Hansen–Zheng Theorem among other things. [Copyright &y& Elsevier]

Abstract: Ridges are one of the key features of interest in areas such as computer vision and image processing. Even though a significant amount of research has been directed to defining and extracting ridges some fundamental challenges remain. For example, the most popular ridge definition (height ridge) is not invariant under monotonic transformations and its global structure is typically ignored during numerical computations. Furthermore, many existing algorithms are based on numerical heuristics and are rarely guaranteed to produce consistent results. This paper reexamines a slightly different ridge definition that is consistent with all desired invariants. Nevertheless, we show that this definition results in similar structures compared to height ridges and that both formulations are equivalent for quadratic functions. Furthermore, this definition can be cast in the form of a degenerate Jacobi set, which allows insights into the global structure of ridges. In particular, we introduce the Ridge–Valley graph as the complete description of all ridges in an image. Finally, using the connection to Jacobi sets we describe a new combinatorial algorithm to extract the Ridge–Valley graph from sampled images guaranteed to produce a valid structure. [Copyright &y& Elsevier]

Abstract: A graph is a square root of a graph if two vertices are adjacent in if and only if they are at distance one or two in . Computing a square root of a given graph is NP-hard, even when the input graph is restricted to be chordal. In this paper, we show that computing a square root can be done in linear time for a well-known subclass of chordal graphs, the class of trivially perfect graphs. This result is obtained by developing a structural characterization of graphs that have a split square root. We also develop linear time algorithms for determining whether a threshold graph given either by a degree sequence or by a separating structure has a square root. [Copyright &y& Elsevier]

Abstract: For a positive integer , a -dominating set of a graph is a subset such that every vertex not in is adjacent to at least vertices in . The -domination problem is to determine a minimum -dominating set of . This paper studies the -domination problem in graphs from an algorithmic point of view. In particular, we present a linear-time algorithm for the -domination problem for graphs in which each block is a clique, a cycle or a complete bipartite graph. This class of graphs includes trees, block graphs, cacti and block-cactus graphs. We also establish NP-completeness of the -domination problem in split graphs. [Copyright &y& Elsevier]

Abstract: A sigraph is a graph in which each edge carries a value called its sign, denoted specially as . Given a sigraph , a new sigraph , called the common-edge sigraph of is that sigraph whose vertex-set is the set of pairs of adjacent edges in and two vertices of are adjacent if the corresponding pairs of adjacent edges of have exactly one edge in common, and the sign of the edge is the sign of the common edge. If all the edges of the sigraph carry + sign then is actually a graph and the corresponding common-edge sigraph is termed as the common-edge graph. In this paper, we characterize common-edge graph and common-edge sigraph and write an algorithm to obtain a corresponding common-edge root graph and common-edge root sigraph from a given common-edge graph and common-edge sigraph respectively. [Copyright &y& Elsevier]

Abstract: A set of a graph is a liar’s dominating set if for all , and for every pair of distinct vertices, . A graph admits a liar’s dominating set if each of its connected component has at least three vertices. Given a graph and an integer , the liar’s domination decision problem (LR-DOMDP) is to decide whether has a liar’s dominating set of cardinality at most . Slater [P.J. Slater, Liar’s Domination, Networks, 54(2) (2009) 70–74] proved that the LR-DOMDP is NP-complete for general graphs. Subsequently, Roden and Slater [M.L. Roden and P.J. Slater, Liar’s domination in graphs, Discrete Math., 309(19) (2009) 5884–5890] showed a more general family of problems to each be NP-complete for bipartite graphs. Besides this result, no other algorithmic result for the liar’s dominating set problem is available in the literature. In this paper, we first strengthen the complexity result of the LR-DOMDP by showing that this problem remains NP-complete for split graphs and hence for chordal graphs. Finally, we propose a linear time algorithm for computing a minimum cardinality liar’s dominating set in a tree. [Copyright &y& Elsevier]

Abstract: The maximum induced matching problem is known to be APX-hard in the class of bipartite graphs. Moreover, the problem is also intractable in this class from a parameterized point of view, i.e. it is W[1]-hard. In this paper, we reveal several classes of bipartite (and more general) graphs for which the problem admits fixed-parameter tractable algorithms. We also study the computational complexity of the problem for regular bipartite graphs and prove that the problem remains APX-hard even under this restriction. On the other hand, we show that for hypercubes (a proper subclass of regular bipartite graphs) the problem admits a simple solution. [Copyright &y& Elsevier]

Abstract: A mixed dominating set of a simple graph is a subset such that every vertex or edge not in is adjacent or incident to at least one vertex or edge in . The mixed domination problem is to determine a minimum mixed dominating set of . This paper studies mixed domination in graphs from an algorithmic point of view. In particular, a linear-time labeling algorithm for the mixed domination problem in cacti is presented. In addition, we fix an incomplete proof of the NP-completeness of the mixed domination problem in split graphs Zhao et al. (2011) [23]. Finally, we establish a primal–dual algorithm for the mixed domination problem in trees. [Copyright &y& Elsevier]

Abstract: Let denote a graph class. An undirected graph is called a probe graph if one can make a graph in by adding edges between vertices in some independent set of . By definition graph class is a subclass of probe graphs. A graph is distance hereditary if the distance between any two vertices remains the same in every connected induced subgraph. Bipartite distance-hereditary graphs are both bipartite and distance hereditary. In this paper we propose -time algorithms to recognize probe distance-hereditary graphs and probe bipartite distance-hereditary graphs where and are the numbers of vertices and edges of the input graph respectively. [Copyright &y& Elsevier]

Abstract: In this paper, we introduce an generic framework for the mining of sequences under various constraints. More precisely, we study the enumeration of all partitions of a word into multisets of subsequences. We show that using additional predicates, this generator can be used for frequent subsequences and substrings mining. We define the transition graph whose vertices are multisets of words and arcs are transitions between multisets. We show that is a directed acyclic graph and it admits a covering tree. We use to propose a generic algorithm that enumerates all multisets that satisfies a set of predicates, without redundancy. [Copyright &y& Elsevier]

Abstract: In this paper, we study the class of distance-hereditary comparability graphs, that is, those graphs which admit a transitive orientation and are completely decomposable with respect to the split decomposition. We provide a characterization based on a restricted number of forbidden subgraphs. We also provide further characterizations and one of them, based on the split decomposition, is used to devise a recognizing algorithm working in linear time. Finally, we show how to build distance-hereditary comparability graphs. [Copyright &y& Elsevier]

Abstract: In this paper, we present a framework for object categorization via sketch graphs that incorporate shape and structure information. In this framework, we integrate the learnable And–Or graph model, a hierarchical structure that combines the reconfigurability of a stochastic context free grammar (SCFG) with the constraints of a Markov random field (MRF). Considering the computation efficiency, we generalize instances from the And–Or graph models and perform a set of sequential tests for cascaded object categorization, rather than directly inferring with the And–Or graph models. We study 33 categories, each consisting of a small data set of 30 instances, and 30 additional templates with varied appearance are generalized from the learned And–Or graph model. These samples better span the appearance space and form an augmented training set of 1980 (60×33) training templates. To perform recognition on a testing image, we use a set of sequential tests to project into different representation spaces to narrow the number of candidate matches in . We use “graphlets” (structural elements), as our local features and model at each stage using histograms of graphlets over categories, histograms of graphlets over object instances, histograms of pairs of graphlets over objects, and shape context. Each test is increasingly computationally expensive, and by the end of the cascade we have a small candidate set remaining to use with our most powerful test, a top-down graph matching algorithm. We apply the proposed approach on the challenging public dataset including 33 object categories, and achieve state-of-the-art performance. [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]

Abstract: A graph is called an interval graph if there exists a set of intervals corresponding to the vertex set of and two vertices are adjacent to each other if and only if the two corresponding intervals are intersecting with each other. In this paper, we apply the reliability-based backup 2-center modal proposed by Wang, Wu and Chao, in which each server may fail with a given probability, to interval graphs and present an time algorithm. [Copyright &y& Elsevier]

Abstract: The maximum independent set problem is known to be NP-hard for graphs in general, but is solvable in polynomial time for graphs in many special classes. It is also known that the problem is generally intractable from a parameterized point of view. A simple Ramsey argument implies the fixed-parameter tractability of the maximum independent set problem in classes of graphs of bounded clique number. Beyond this observation very little is known about the parameterized complexity of the problem in restricted graph families. In the present paper we develop fpt-algorithms for graphs in some classes extending graphs of bounded clique number. [Copyright &y& Elsevier]

Abstract: Let be a graph and be an assignment of thresholds to the vertices of . A subset of vertices is said to be a dynamic monopoly corresponding to if the vertices of can be partitioned into subsets such that and for any , each vertex in has at least neighbors in . Dynamic monopolies are in fact modeling the irreversible spread of influence in social networks. In this paper we first obtain a lower bound for the smallest size of any dynamic monopoly in terms of the average threshold and the order of graph. Also we obtain an upper bound in terms of the minimum vertex cover of graphs. Then we derive the upper bound for the smallest size of any dynamic monopoly when the graph contains at least one odd vertex, where the threshold of any vertex is set as (i.e. strict majority threshold). This bound improves the best known bound for strict majority threshold. We show that the latter bound can be achieved by a polynomial time algorithm. We also show that is an upper bound for the size of strict majority dynamic monopoly, where stands for the matching number of . Finally, we obtain a basic upper bound for the smallest size of any dynamic monopoly, in terms of the average threshold and vertex degrees. Using this bound we derive some other upper bounds. [Copyright &y& Elsevier]

Abstract: A maximum stable set in a graph is a stable set of maximum cardinality. is a local maximum stable set of , and we write , if is a maximum stable set of the subgraph induced by , where is the neighborhood of . A greedoid is called a local maximum stable set greedoid if there exists a graph such that . Nemhauser and Trotter Jr. (1975) , proved that any is a subset of a maximum stable set of . In Levit and Mandrescu (2002) we have shown that the family of a forest forms a greedoid on its vertex set. The cases where is bipartite, triangle-free, well-covered, unicycle, while is a greedoid, were analyzed in Levit and Mandrescu (2004, 2007, 2008, 2001, 2009) , respectively. In this paper, we demonstrate that if the family satisfies the accessibility property, then, first, is a greedoid, and, second, this greedoid, which we called the local maximum stable set greedoid defined by , is an interval greedoid. We also characterize those graphs whose families of local maximum stable sets are either antimatroids or matroids. For these cases, some polynomial recognition algorithms are suggested. [Copyright &y& Elsevier]

Abstract: In this paper we present a method to simulate, using the bit-parallelism technique, the nondeterministic Aho–Corasick automaton and the nondeterministic suffix automaton induced by the trie and by the Directed Acyclic Word Graph for a set of patterns, respectively. When the prefix redundancy is nonnegligible, this method yields—if compared to the original bit-parallel encoding with no prefix factorization—a representation that requires smaller bit-vectors and, correspondingly, less words. In particular, if we restrict to single-word bit-vectors, more patterns can be packed into a word. We also present two simple algorithms, based on such a technique, for searching a set of patterns in a text T of length n over an alphabet Σ of size σ. Our algorithms, named Log-And and Backward-Log-And, require -space, and work in and worst-case searching time, respectively, where w is the number of bits in a computer word, m is the number of states of the automaton, and is the length of the shortest pattern in . [Copyright &y& Elsevier]

Abstract: This paper is aimed at investigating some computational aspects of different isoperimetric problems on weighted trees. In this regard, we consider different connectivity parameters called minimum normalized cuts/isoperimetric numbers defined through taking the minimum of the maximum or the mean of the normalized outgoing flows from a set of subdomains of vertices, where these subdomains constitute a partition/subpartition. We show that the decision problem for the case of taking -partitions and the maximum (called the max normalized cut problem NCP), and the other two decision problems for the mean version (referred to as IPP and NCP) are -complete problems for weighted trees. On the other hand, we show that the decision problem for the case of taking -subpartitions and the maximum (called the max isoperimetric problem IPP) can be solved in linear time for any weighted tree and any . On the basis of this fact, we provide polynomial time -approximation algorithms for all different versions of the th isoperimetric numbers considered. Moreover, for when the number of partitions/subpartitions, , is a fixed constant, we prove, as an extension of a result of Mohar (1989) for the case (usually referred to as the Cheeger constant), that the max and mean isoperimetric numbers of weighted trees, and their max minimum normalized cut can be computed in polynomial time. We also prove some hardness results for the case of simple unweighted graphs and trees. [Copyright &y& Elsevier]

Abstract: In this paper, we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number and the harmonious chromatic number of -tidy graphs and ()-graphs, for every fixed q. These classes include cographs, -sparse and -lite graphs. We also obtain a polynomial time algorithm to determine the Grundy number of ()-graphs. All these coloring problems are known to be NP-hard for general graphs. [Copyright &y& Elsevier]

Abstract: Recently, sparsity preserving projections (SPP) algorithm has been proposed, which combines l 1-graph preserving the sparse reconstructive relationship of the data with the classical dimensionality reduction algorithm. However, when applied to classification problem, SPP only focuses on the sparse structure but ignores the label information of samples. To enhance the classification performance, a new algorithm termed discriminative learning by sparse representation projections or DLSP for short is proposed in this paper. DLSP algorithm incorporates the merits of both local interclass geometrical structure and sparsity property. That makes it possess the advantages of the sparse reconstruction, and more importantly, it has better capacity of discrimination, especially when the size of the training set is small. Extensive experimental results on serval publicly available data sets show the feasibility and effectiveness of the proposed algorithm. [Copyright &y& Elsevier]

Abstract: In this paper, we introduce the upgrading problem of edge-disjoint paths. In the off-line upgrading problem, a supply graph with integer capacities and two demand graphs and with unit demands are given on the same vertex set. Our task is to determine the maximum size of a set such that has an integer routing in which can be extended both to an integer routing of and to an integer routing of . In the online upgrading problem, we are given a supply graph with integer capacities, a demand graph with an integer routing, and another demand graph with unit demands such that . Our task is to determine the maximum size of a set such that the restriction of the given routing to can be extended to an integer routing of . Thus, depending on whether the graphs are directed or undirected, we have four different versions. We give algorithmic proofs of minimax formulas for the case when is a ring and the demand graphs are stars with the same center. All four versions are NP-complete for general graphs. [Copyright &y& Elsevier]

Abstract: We consider the problem of matching people to items, where each person ranks a subset of items in an order of preference, possibly involving ties. There are several notions of optimality about how to best match a person to an item; in particular, popularity is a natural and appealing notion of optimality. A matching is popular if there is no matching such that the number of people who prefer to exceeds the number who prefer to . However, popular matchings do not always provide an answer to the problem of determining an optimal matching since there are simple instances that do not admit popular matchings. This motivates the following extension of the popular matchings problem: [•] Given a graph where is the set of people and is the set of items, and a list denoting upper bounds on the number of copies of each item, does there exist such that for each , having copies of the -th item, where , enables the resulting graph to admit a popular matching? In this paper we show that the above problem is NP-hard. We show that the problem is NP-hard even when each is 1 or 2. We show a polynomial time algorithm for a variant of the above problem where the total increase in copies is bounded by an integer . [Copyright &y& Elsevier]

Abstract: In a capacitated graph with a set of commodities, the sparsity of a cut is the ratio between the capacity of the cut and the demand of the commodities separated by the cut. The Sparsest Cut (SC) is often introduced as a weak dual of the Maximum Concurrent Flow problem (MCF). Contrarily to MCF, problem SC is, in general, NP-hard. This problem has been considerably studied, motivating the design of very elaborated approximation algorithms [Auman, Y. and Y. Rabani, Approximate min-cut max-flow theorem and approximations algorithm, SIAM Journal on Computing 27 (1998), pp. 213–238] [Günlük, O., On the min-cut max-flow ratio for multicommodity flows, SIAMJ. of Disc. Math. 21 (2007), pp. 1–15] [N. Garg, M. Y., V. Vazirani, Approximate max-flow min-(multi)cut theorems and their applications, in: STOC''93, 1993, pp. 698–707] [S. Plotkin, E. T., Improved bounds on the max-flow min-cut ratio for multicommodity flows, in: 25th Symposium on Theory of Computing, 1993] [Tragoudas, S., Improved approximations for the min-cut max-flow ratio and the flux, Mathematical Systems Theory 29 (1996), pp. 157–167]. Somewhat surprisingly, to the best of our knowledge, problem (SC) has not been investigated with exact approaches using Mixed Integer Programming models. In this paper, we propose a formulation arising “naturally” from the dual of (MCF). [Copyright &y& Elsevier]

Abstract: Given an -vertex directed graph and a set of requests, we consider assigning a set of edges to each vertex in so that for every request in the union of the edge sets assigned to and contains a path from to . The Minimum Certificate Dispersal Problem (MCD) is defined as one to find an assignment that minimizes the sum of the cardinalities of the edge sets assigned to each vertex. This problem has been shown to be NP-hard in general, though it is polynomially solvable for some restricted classes of graphs and restricted request structures, such as bidirectional trees with requests of all pairs of vertices. In this paper, we give an advanced investigation about the difficulty of MCD by focusing on the relationship between its (in)approximability and request structures. We first show that MCD with general has lower and upper bounds on approximation ratio under the assumption . We then assume forms a clique structure, called Subset-Full, which is a natural setting in the context of the application. Interestingly, under this natural setting, MCD becomes 2-approximable, though it has still no polynomial time approximation algorithm whose factor is better than 677/676 unless . Finally, we show that this approximation ratio can be improved to 3/2 for the undirected variant of MCD with Subset-Full. [Copyright &y& Elsevier]