19 results on '"Clique-width"'
Search Results
2. Fly-automata for checking monadic second-order properties of graphs of bounded tree-width.
- Author
-
Courcelle, Bruno
- Abstract
Every graph property expressible in monadic second-order (MSO) logic, can be checked in linear time on graphs of bounded tree-width by means of finite automata running on terms denoting tree-decompositions. Implementing these automata is difficult because of their huge sizes. Fly-automata (FA) are deterministic automata that compute the necessary states and transitions when running (instead of looking into tables ); they overcome this difficulty. Previously, we constructed FA to check MSO properties of graphs of bounded clique-width . An MSO property with edge quantifications (called an MSO 2 property) is an MSO property of the incidence graph and, graphs of tree-width k have incidence graphs of clique-width O ( k ) . Our existing constructions can be used for MSO 2 properties of graphs of bounded tree-width. We examine concrete aspects of this adaptation. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
3. Bounding the Clique-Width of H-free Split Graphs.
- Author
-
Brandstädt, Andreas, Dabrowski, Konrad K., Huang, Shenwei, and Paulusma, Daniël
- Abstract
A graph is H -free if it has no induced subgraph isomorphic to H . We continue a study into the boundedness of clique-width of subclasses of perfect graphs. We identify five new classes of H -free split graphs whose clique-width is bounded. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs H for which the class of H -free split graphs has bounded clique-width. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
4. A new representation of proper interval graphs with an application to clique-width.
- Author
-
Heggernes, Pinar, Meister, Daniel, and Papadopoulos, Charis
- Subjects
INTERSECTION graph theory ,REPRESENTATIONS of graphs ,GRAPH labelings ,PARTITIONS (Mathematics) ,SET theory ,MATHEMATICAL models - Abstract
Abstract: We introduce a new representation of proper interval graphs that can be computed in linear time and stored in space. This representation is a 2-dimensional vertex partition. It is particularly interesting with respect to clique-width. Based on this representation, we prove new upper bounds on the clique-width of proper interval graphs. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
5. Fly-automata for checking monadic second-order properties of graphs of bounded tree-width
- Author
-
Bruno Courcelle
- Subjects
Block graph ,Discrete mathematics ,TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES ,Applied Mathematics ,1-planar graph ,Combinatorics ,Treewidth ,Indifference graph ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Pathwidth ,Chordal graph ,Clique-width ,Discrete Mathematics and Combinatorics ,Graph property ,Computer Science::Formal Languages and Automata Theory ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
Every graph property expressible in monadic second-order (MSO) logic, can be checked in linear time on graphs of bounded tree-width by means of finite automata running on terms denoting tree-decompositions. Implementing these automata is difficult because of their huge sizes. Fly-automata (FA) are deterministic automata that compute the necessary states and transitions when running (instead of looking into tables); they overcome this difficulty. Previously, we constructed FA to check MSO properties of graphs of bounded clique-width. An MSO property with edge quantifications (called an MSO2 property) is an MSO property of the incidence graph and, graphs of tree-width k have incidence graphs of clique-width O ( k ) . Our existing constructions can be used for MSO2 properties of graphs of bounded tree-width. We examine concrete aspects of this adaptation.
- Published
- 2015
6. Minimum Size Tree-decompositions
- Author
-
Karol Suchan, Fatima Zahra Moataz, Bi Li, and Nicolas Nisse
- Subjects
Discrete mathematics ,Applied Mathematics ,0207 environmental engineering ,0102 computer and information sciences ,02 engineering and technology ,Tree-depth ,01 natural sciences ,1-planar graph ,Tree decomposition ,Combinatorics ,Treewidth ,Pathwidth ,010201 computation theory & mathematics ,Chordal graph ,Partial k-tree ,Clique-width ,Discrete Mathematics and Combinatorics ,020701 environmental engineering ,Mathematics - Abstract
Tree-decompositions are the cornerstone of many dynamic programming algorithms for solving graph problems. Since the complexity of such algorithms generally depends exponentially on the width (size of the bags) of the decomposition, much work has been devoted to compute tree-decompositions with small width. However, practical algorithms computing tree-decompositions only exist for graphs with treewidth less than 4. In such graphs, the time-complexity of dynamic programming algorithms is dominated by the size (number of bags) of the tree-decompositions. It is then interesting to minimize the size of the tree-decompositions. In this extended abstract, we consider the problem of computing a tree-decomposition of a graph with width at most k and minimum size. We prove that the problem is NP-complete for any fixed k ≥ 4 and polynomial for k ≤ 2; for k = 3, we show that it is polynomial in the class of trees and 2-connected outerplanar graphs.
- Published
- 2015
7. Bipartite operator decomposition of graphs and the reconstruction conjecture
- Author
-
Regina Tyshkevich and Pavel Skums
- Subjects
Combinatorics ,Discrete mathematics ,Edge-transitive graph ,Graph power ,Applied Mathematics ,Clique-width ,Voltage graph ,Graph minor ,Discrete Mathematics and Combinatorics ,Cubic graph ,Complete bipartite graph ,Complement graph ,Mathematics - Abstract
We consider a binary operation • on the set of triads ( G , A , B ) , where G is a graph and ( A , B ) is the partition of the set of the set V ( G ) . The operation • of multiplication of a triad and a graph is defined and the properties of the introduced operations are described. We study in detail the subcase, when the triads have the form ( G , A , B ) , where G is a bipartite graph and ( A , B ) is its bipartition. For this case the decomposition theorem stating that any graph except the described family of exceptions can be uniquely decomposed into indecomposable components with respect to the operation • is proved. Using this theorem, we proved the following. Let the graph G have a module M with associated partition ( A , B , M ) , where A ∼ M and B ≁ M , such that G [ A ∪ B ] is a bipartite graph with bipartition ( A , B ) . Then the graph G is reconstructible.
- Published
- 2007
8. Characterizing –partitionable Cographs
- Author
-
Raquel de Souza Francisco, Sulamita Klein, and Loana Tito Nogueira
- Subjects
Combinatorics ,Discrete mathematics ,Pathwidth ,Chordal graph ,Applied Mathematics ,Clique-width ,Discrete Mathematics and Combinatorics ,Comparability graph ,Cograph ,Split graph ,Forbidden graph characterization ,Distance-hereditary graph ,Mathematics - Abstract
We consider the problem of partitioning a graph into k independent sets and l cliques, known as the ( k , l ) -partition problem, which was introduced by Brandstadt in [A. Bransdstadt, Partitions of graphs into one or two independent sets and cliques, Discrete Mathematics 152 (1996) 47–54], and generalized by Feder et al. in [T. Feder, P. Hell, S. Klein, and R. Motwani, Complexity of graph partition problems, in: Thirty First Annual ACM Symposium on Theory of Computing (1999), Plenum Press, New York, 1999, 464–472] as the M-partition problem. Brandstadt proved that given a graph G, it is NP-complete to decide if G is a ( k , l ) -graph for k ≥ 3 or l ≥ 3 . Since then, a lot of work have been done in order to solve the ( k , l ) -partition problem for many subclasses of perfect graphs. In this work, we consider a subclass of perfect graphs: the cographs, which correspond to graphs without paths with size 4. More precisely, we provide a characterization of cographs that are ( k , l ) -graphs by forbidden configurations, that is, a cograph G is a ( k , l ) -graph if and only if it does not contain any of the forbbiden configurations.
- Published
- 2005
9. Connected Graph Searching in Outerplanar Graphs
- Author
-
Fedor V. Fomin, Ioan Todinca, and Dimitrios M. Thilikos
- Subjects
Computer Science::Information Retrieval ,Applied Mathematics ,Butterfly graph ,Biconnected graph ,law.invention ,Planar graph ,Combinatorics ,Search game ,symbols.namesake ,Pathwidth ,law ,Line graph ,Clique-width ,symbols ,Discrete Mathematics and Combinatorics ,Null graph ,Mathematics - Abstract
Search games are a powerfull tool for studying various connectivity parameters of graphs. In the classical search game, we consider an undirected graph G = (V, E) whose edges are initially contaminated. A set of searchers try to clean the graph. At the beginning the graph contains no searchers. At each step of the game, a searcher can be placed on an arbitrary vertex of the graph or, if the searcher is already on a vertex v it can slide through an edge e incident to v. In the former case the edge e is cleaned by the searcher. If, for some clean edge e, there is a path from e to a contaminated edge such that no searcher separates the two edges on the path, then e becomes recontaminated. The search number s(G) of G is the minimum number of searchers required to clean all the edges of G. The search number differs by at most one from another well-known graph parameter, namely the pathwidth. The treewidth, the branchwidth and several parameters of the same flavour can be defined by versions of the search game. In this paper we consider a variant of the search game introduced by Barriere et al. [1], called connected search. It requires that, at each step of the search game
- Published
- 2005
10. Graph decompositions definable in monadic second-order logic
- Author
-
Bruno Courcelle
- Subjects
Discrete mathematics ,Applied Mathematics ,Voltage graph ,law.invention ,Combinatorics ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,law ,Computer Science::Logic in Computer Science ,Clique-width ,Line graph ,Graph minor ,Discrete Mathematics and Combinatorics ,Cubic graph ,Null graph ,Graph property ,Complement graph ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
We prove that the split decomposition of a graph is definable by Monadic Second-Order formulas. We also prove that the set of graphs having the same cycle matroid as a given graph is definable from this graph by Monadic Second-Order formulas. These results are consequences of general results on the logical definability of graph decompositions of various types.
- Published
- 2005
11. Graph decompositions for cartesian products
- Author
-
Selma Djelloul
- Subjects
Discrete mathematics ,Applied Mathematics ,Tree-depth ,1-planar graph ,Treewidth ,Combinatorics ,Pathwidth ,Partial k-tree ,Clique-width ,Discrete Mathematics and Combinatorics ,Lattice graph ,Graph product ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
In this paper we describe an algorithmic construction that, given a tree-decomposition of a graph G and a path-decomposition of a graph H , provides a tree-decomposition of the cartesian product of G and H . From the latter, we derive upper bounds on the treewidth and on the pathwidth of the cartesian product, expressed in terms of the treewidth and of the pathwidth of the two involved graphs. On the other hand, in the context of graph grammars and graph logic, we prove that the cartesian product of a class of graphs by a finite set of graphs preserves the property of being a context-free set, and if the graphs in the finite set are all connected, the property of being an MS -definable set is also preserved.
- Published
- 2005
12. Different levels of randomness in Random Ramsey theorems
- Author
-
Miklós Simonovits and Vera T. Sós
- Subjects
Discrete mathematics ,Random graph ,Applied Mathematics ,Symmetric graph ,law.invention ,Extremal graph theory ,Combinatorics ,law ,Random regular graph ,Clique-width ,Line graph ,Discrete Mathematics and Combinatorics ,Forbidden graph characterization ,Universal graph ,Mathematics - Abstract
Extremal graph theory, Ramsey theory and the theory of Random graphs are strongly connected to each other. Starting from these fields, we formulate some problems and results which are related to different levels of randomness. The first one is completely non-random, being the ordinary Ramsey-Turan problem and in the subsequent three problems we formulate some randomized variations of the problem. Speaking of graph properties, we shall consider them as sets of graphs and occasionally write G ∈ P instead of writing that G has property P. A graph property P is called monotone if adding an edge to a H n ∈ P, we get an H ∗ n ∈ P. We shall use three models of random graphs: the binomial, the hypergeometric and the stopping-rule model. This abstract contains the most important definitions.
- Published
- 2003
13. Using an Incomplete Version of Dynamic Backtracking for Graph Colouring
- Author
-
Steven Prestwich
- Subjects
Discrete mathematics ,Block graph ,Backtracking ,Applied Mathematics ,Comparability graph ,law.invention ,Constraint graph ,law ,Outerplanar graph ,Line graph ,Clique-width ,Discrete Mathematics and Combinatorics ,Graph property ,Mathematics - Abstract
This paper investigates a simple, constructive search strategy: an incomplete version of Ginsberg's Dynamic Backtracking which records no information during search, and randomly selects variables for backtracking. Combining this with forward checking and dynamic variable ordering heuristics we obtain algorithms for constraint satisfaction problems, and by adding branch-and-bound we obtain optimization algorithms. Testing these on several classes of 1000-vertex graph colouring problems we find colourings which are competitive with those of specialized algorithms: a 92-colouring for a random graph (p = 0.5), hidden k-colourings in equipartite graphs (p = 0.5) for k ≤ 60 and improved results for geometric graphs. An interesting aspect is that most of our results were obtained using the precise opposite of the well-known first-fail principle.
- Published
- 1999
14. Generalization of Splitting off Operation to Binary Matroids
- Author
-
M.M. Shikare Ghodratollaha Azadi and B.N. Waphare
- Subjects
Discrete mathematics ,Computer science ,Applied Mathematics ,Symmetric graph ,Voltage graph ,Strength of a graph ,law.invention ,Combinatorics ,law ,Line graph ,Clique-width ,Discrete Mathematics and Combinatorics ,Null graph ,Graph product ,Complement graph - Abstract
The splitting off operation for graphs is defined in the following way: Let G be a graph. Given incident edges x = vv1 and y = vv2 in G, we can construct a new graph Gxy by adding the edge v1v2 and deleting the edges x and y. If v1 = v2, then the resulting loop is deleted. The transition from G to Gxy is called the splitting off operation. The splitting off operation has important applications in graph theory (for example, see Frank A., Augmenting graphs to meet edge-connectivity requirements, SIAM J. of Discrete Mathematics 5 No.1. (1992), 22-53; Jordan T., Edge-Splitting Problems With Demands, Springer LINK: Lecture Notes in Computer Science 1610, (1999); and Lovasz L., Combinatorial Problems and Exercises, North Holland, Amsterdam (1979)). We characterize the circuits of the graph Gxy in terms of the circuits of G.
- Published
- 2003
15. Partial Complement of a Graph
- Author
-
Hanumappa B. Walikar
- Subjects
Combinatorics ,Applied Mathematics ,Clique-width ,Discrete Mathematics and Combinatorics ,Comparability graph ,Null graph ,Graph property ,Complement graph ,Simplex graph ,Mathematics - Published
- 2003
16. Clique-width of countable graphs: a compactness property
- Author
-
Bruno Courcelle
- Subjects
Block graph ,Discrete mathematics ,Clique-width ,Logic ,Applied Mathematics ,Mathematics::General Topology ,Clique graph ,Theoretical Computer Science ,law.invention ,Combinatorics ,Mathematics::Logic ,Vertex-transitive graph ,Computer Science::Discrete Mathematics ,law ,Line graph ,Countable set ,Discrete Mathematics and Combinatorics ,Perfect graph theorem ,Cograph ,Split graph ,Countable graph ,Mathematics ,Universal graph - Abstract
We define the clique-width of a countable graph. We prove that a countable graph has finite clique-width iff its finite induced subgraphs have bounded clique-width. We obtain an application to a conjecture concerning the structure of sets of countable graphs having a decidable monadic second-order satisfiability problem.
- Published
- 2000
17. DIMAP Workshop on Algorithmic Graph Theory
- Author
-
Vadim V. Lozin and Arie M. C. A. Koster
- Subjects
Discrete mathematics ,Theoretical computer science ,Graph labeling ,Computer science ,Applied Mathematics ,Voltage graph ,Algorithmic graph theory ,law.invention ,law ,Line graph ,Clique-width ,Discrete Mathematics and Combinatorics ,Graph (abstract data type) ,Graph property ,Null graph - Published
- 2009
18. On probe classes of graphs
- Author
-
Daniel Bayer, Van Bang Le, and H. N. de Ridder
- Subjects
Discrete mathematics ,Applied Mathematics ,Graph ,law.invention ,Combinatorics ,law ,Outerplanar graph ,Clique-width ,Line graph ,Discrete Mathematics and Combinatorics ,Topological graph theory ,Split graph ,Graph isomorphism ,Universal graph ,Mathematics - Published
- 2006
19. Bipartite Graphs and their Degree Sets
- Author
-
Yannis Manoussakis and H. P. Patil
- Subjects
Discrete mathematics ,Applied Mathematics ,Voltage graph ,Complete bipartite graph ,law.invention ,Combinatorics ,Vertex-transitive graph ,Edge-transitive graph ,law ,Graph power ,Line graph ,Clique-width ,Bipartite graph ,Discrete Mathematics and Combinatorics ,Mathematics - Abstract
The degree set D(G) of a graph G is the set of degrees of G. Given a finite, nonempty set S of positive integers, it is shown that there exists a bipartite graph G such that D ( G ) = S . In addition, the minimum order of such a graph is determined when it is either unicyclic or connected. Furthermore, for any two sets S and T of positive integers of the same cardinality, it is shown that there exists a bipartite graph B(X, Y) such that D ( X ) = S , D ( Y ) = T . Moreover, the minimum of order of such a connected bipartite graph is obtained.
- Published
- 2003
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.