Search results for "Clique-width"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
147	Derek G. Corneil, Udi Rotics	On the Relationship between Clique-Width and Treewidth.	WG	2001	DBLP DOI BibTeX RDF
144	Sang-il Oum	Approximating Rank-Width and Clique-Width Quickly.	WG	2005	DBLP DOI BibTeX RDF
135	Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider	Clique-width minimization is NP-hard.	STOC	2006	DBLP DOI BibTeX RDF	absolute approximation, NP-completeness, clique-width, pathwidth
133	Martin Charles Golumbic, Udi Rotics	On the Clique-Width of Perfect Graph Classes.	WG	1999	DBLP DOI BibTeX RDF
120	Pinar Heggernes, Daniel Meister 0001, Charis Papadopoulos	A Complete Characterisation of the Linear Clique-Width of Path Powers.	TAMC	2009	DBLP DOI BibTeX RDF
115	Frank Gurski, Egon Wanke	The Clique-Width of Tree-Power and Leaf-Power Graphs.	WG	2007	DBLP DOI BibTeX RDF	tree powers, NLC-width, strictly chordal, tree-width, clique-width, leaf powers
114	Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh 0001	Clique-width: on the price of generality.	SODA	2009	DBLP DOI BibTeX RDF
105	Amir H. Farrahi, D. T. Lee, Majid Sarrafzadeh	Two-Way and Multiway Partitioning of a Set of Intervals for Clique-Width Maximization.	Algorithmica	1999	DBLP DOI BibTeX RDF	Partitioning, Interval graphs, Sleep mode, Clique-width
104	Omer Giménez, Petr Hlinený, Marc Noy	Computing the Tutte Polynomial on Graphs of Bounded Clique-Width.	WG	2005	DBLP DOI BibTeX RDF	subexponential algorithm, U polynomial, cographs, clique-width, Tutte polynomial
101	Vadim V. Lozin	From Tree-Width to Clique-Width: Excluding a Unit Interval Graph.	ISAAC	2008	DBLP DOI BibTeX RDF	Unit interval graphs, Fixed parameter tractability, Tree-width, Clique-width
98	Sang-il Oum	Approximating rank-width and clique-width quickly.	ACM Trans. Algorithms	2008	DBLP DOI BibTeX RDF	rank-width, Approximation algorithms, matroids, clique-width, branch-width
94	Bruno Courcelle, Mamadou Moustapha Kanté	Graph Operations Characterizing Rank-Width and Balanced Graph Expressions.	WG	2007	DBLP DOI BibTeX RDF
92	Andreas Brandstädt, Feodor F. Dragan, Hoàng-Oanh Le, Raffaele Mosca	New Graph Classes of Bounded Clique-Width.	Theory Comput. Syst.	2005	DBLP DOI BibTeX RDF
92	Alexander Glikson, Johann A. Makowsky	NCE Graph Grammars and Clique-Width.	WG	2003	DBLP DOI BibTeX RDF
92	Andreas Brandstädt, Feodor F. Dragan, Hoàng-Oanh Le, Raffaele Mosca	New Graph Classes of Bounded Clique-Width.	WG	2002	DBLP DOI BibTeX RDF
86	Frank Gurski, Egon Wanke	Minimizing NLC-Width is NP-Complete.	WG	2005	DBLP DOI BibTeX RDF
85	Binh-Minh Bui-Xuan, Jan Arne Telle, Martin Vatshelle	Boolean-Width of Graphs.	IWPEC	2009	DBLP DOI BibTeX RDF
78	Andreas Brandstädt, Joost Engelfriet, Hoàng-Oanh Le, Vadim V. Lozin	Clique-Width for 4-Vertex Forbidden Subgraphs.	Theory Comput. Syst.	2006	DBLP DOI BibTeX RDF
78	Andreas Brandstädt, Joost Engelfriet, Hoàng-Oanh Le, Vadim V. Lozin	Clique-Width for Four-Vertex Forbidden Subgraphs.	FCT	2005	DBLP DOI BibTeX RDF
78	Jan Obdrzálek	Clique-Width and Parity Games.	CSL	2007	DBLP DOI BibTeX RDF
72	Feodor F. Dragan, Chenyu Yan	Collective Tree Spanners in Graphs with Bounded Genus, Chordality, Tree-Width, or Clique-Width.	ISAAC	2005	DBLP DOI BibTeX RDF
72	Frank Gurski, Egon Wanke	The Tree-Width of Clique-Width Bounded Graphs Without Kn, n.	WG	2000	DBLP DOI BibTeX RDF
69	Naomi Nishimura, Prabhakar Ragde, Stefan Szeider	Solving #SAT using vertex covers.	Acta Informatica	2007	DBLP DOI BibTeX RDF
69	Naomi Nishimura, Prabhakar Ragde, Stefan Szeider	Solving #SAT Using Vertex Covers.	SAT	2006	DBLP DOI BibTeX RDF
69	Georg Gottlob, Reinhard Pichler	Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width.	ICALP	2001	DBLP DOI BibTeX RDF
66	Nicholas Korpelainen, Vadim V. Lozin	Bipartite Graphs of Large Clique-Width.	IWOCA	2009	DBLP DOI BibTeX RDF	Hereditary class, Tree-width, Clique-width
66	Daniel Kobler, Udi Rotics	Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract).	SODA	2001	DBLP BibTeX RDF	coloring, dominating set, polynomial algorithms, edge-coloring, clique-width, edge-dominating set
64	Bruno Courcelle, Johann A. Makowsky, Udi Rotics	Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width.	WG	1998	DBLP DOI BibTeX RDF
64	Pascal Koiran, Klaus Meer	On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width.	WG	2008	DBLP DOI BibTeX RDF
61	Frank Gurski, Egon Wanke	Vertex Disjoint Paths on Clique-Width Bounded Graphs.	LATIN	2004	DBLP DOI BibTeX RDF
57	Andreas Brandstädt	On Robust Algorithms for the Maximum Weight Stable Set Problem.	FCT	2001	DBLP DOI BibTeX RDF	Maximum Weight Stable Set Problem on graphs, modules and homogeneous sets in graphs, graph structure, clique width, robust algorithms, prime graphs
52	Robert Ganian, Petr Hlinený, Joachim Kneis, Alexander Langer, Jan Obdrzálek, Peter Rossmanith	On Digraph Width Measures in Parameterized Algorithmics.	IWPEC	2009	DBLP DOI BibTeX RDF
52	Wolfgang Espelage, Frank Gurski, Egon Wanke	Deciding Clique-Width for Graphs of Bounded Tree-Width.	WADS	2001	DBLP DOI BibTeX RDF
50	Johann A. Makowsky, Udi Rotics, Ilya Averbouch, Benny Godlin	Computing Graph Polynomials on Graphs of Bounded Clique-Width.	WG	2006	DBLP DOI BibTeX RDF
50	Öjvind Johansson	NLC2-Decomposition in Polynomial Time.	WG	1999	DBLP DOI BibTeX RDF
47	Bruno Courcelle, Andrew Twigg	Compact Forbidden-Set Routing.	STACS	2007	DBLP DOI BibTeX RDF	Algorithms, compact routing, labelling schemes
47	Öjvind Johansson	log n-Approximative NLCk-Decomposition in O(n2k+1) Time.	WG	2001	DBLP DOI BibTeX RDF
44	Bogdan Alecu, Mamadou Moustapha Kanté, Vadim V. Lozin, Viktor Zamaraev	Between clique-width and linear clique-width of bipartite graphs.	Discret. Math.	2020	DBLP DOI BibTeX RDF
44	Daniel Meister 0001, Udi Rotics	Minimal forbidden induced subgraphs of graphs of bounded clique-width and bounded linear clique-width.	CoRR	2013	DBLP BibTeX RDF
44	Pinar Heggernes, Daniel Meister 0001, Udi Rotics	Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width.	CSR	2011	DBLP DOI BibTeX RDF
44	Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider	Proving NP-hardness for clique-width II: non-approximability of clique-width	Electron. Colloquium Comput. Complex.	2005	DBLP BibTeX RDF
44	Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider	Proving NP-hardness for clique-width I: non-approximability of sequential clique-width	Electron. Colloquium Comput. Complex.	2005	DBLP BibTeX RDF
43	Andreas Brandstädt, Christian Hundt 0001	Ptolemaic Graphs and Interval Graphs Are Leaf Powers.	LATIN	2008	DBLP DOI BibTeX RDF	and Classification Leaf powers, leaf roots, strongly chordal graphs, ptolemaic graphs, graph class inclusions, (unit) interval graphs, clique-width, graph powers
43	Frank Gurski, Egon Wanke	The NLC-width and clique-width for powers of graphs of bounded tree-width.	Discret. Appl. Math.	2009	DBLP DOI BibTeX RDF
42	Wolfgang Espelage, Frank Gurski, Egon Wanke	How to Solve NP-hard Graph Problems on Clique-Width Bounded Graphs in Polynomial Time.	WG	2001	DBLP DOI BibTeX RDF
41	Vít Jelínek	The Rank-Width of the Square Grid.	WG	2008	DBLP DOI BibTeX RDF	rank-width, grid graph
36	Pinar Heggernes, Daniel Meister 0001, Charis Papadopoulos	Graphs of Linear Clique-Width at Most 3.	TAMC	2008	DBLP DOI BibTeX RDF
36	Ioan Todinca	Coloring Powers of Graphs of Bounded Clique-Width.	WG	2003	DBLP DOI BibTeX RDF
36	Rodica Boliac, Vadim V. Lozin	On the Clique-Width of Graphs in Hereditary Classes.	ISAAC	2002	DBLP DOI BibTeX RDF
33	Bernhard Bliem, Sebastian Ordyniak, Stefan Woltran	Clique-Width and Directed Width Measures for Answer-Set Programming.	CoRR	2016	DBLP BibTeX RDF
33	Bernhard Bliem, Sebastian Ordyniak, Stefan Woltran	Clique-Width and Directed Width Measures for Answer-Set Programming.	ECAI	2016	DBLP DOI BibTeX RDF
33	Isolde Adler, Mamadou Moustapha Kanté	Linear rank-width and linear clique-width of trees.	Theor. Comput. Sci.	2015	DBLP DOI BibTeX RDF
33	Martin Fürer	A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width.	CoRR	2014	DBLP BibTeX RDF
33	Martin Fürer	A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width.	LATIN	2014	DBLP DOI BibTeX RDF
33	Isolde Adler, Mamadou Moustapha Kanté	Linear Rank-Width and Linear Clique-Width of Trees.	WG	2013	DBLP DOI BibTeX RDF
33	Hans Adler, Isolde Adler	A note on clique-width and tree-width for structures	CoRR	2008	DBLP BibTeX RDF
33	Eldar Fischer, Johann A. Makowsky, Elena V. Ravve	Counting truth assignments of formulas of bounded tree-width or clique-width.	Discret. Appl. Math.	2008	DBLP DOI BibTeX RDF
33	Karol Suchan, Ioan Todinca	On powers of graphs of bounded NLC-width (clique-width).	Discret. Appl. Math.	2007	DBLP DOI BibTeX RDF
33	Frank Gurski	Characterizations for co-graphs defined by restricted NLC-width or clique-width operations.	Discret. Math.	2006	DBLP DOI BibTeX RDF
33	Sang-il Oum, Paul D. Seymour	Approximating clique-width and branch-width.	J. Comb. Theory, Ser. B	2006	DBLP DOI BibTeX RDF
33	Georg Gottlob, Reinhard Pichler	Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width.	SIAM J. Comput.	2004	DBLP DOI BibTeX RDF
33	Wolfgang Espelage, Frank Gurski, Egon Wanke	Deciding Clique-Width for Graphs of Bounded Tree-Width.	J. Graph Algorithms Appl.	2003	DBLP DOI BibTeX RDF
30	Robert Ganian, Petr Hlinený	Better Polynomial Algorithms on Graphs of Bounded Rank-Width.	IWOCA	2009	DBLP DOI BibTeX RDF	Rank-width, rank-decomposition, chromatic polynomial, Hamiltonian path, chromatic number
30	Petr Hlinený, Sang-il Oum	Finding Branch-Decompositions and Rank-Decompositions.	ESA	2007	DBLP DOI BibTeX RDF	Rank-width, fixed parameter tractable algorithm, graph, matroid, clique-width, branch-width
28	Martin Grohe, György Turán	Learnability and Definability in Trees and Similar Structures.	Theory Comput. Syst.	2004	DBLP DOI BibTeX RDF
28	Martin Grohe, György Turán	Learnability and Definability in Trees and Similar Structures.	STACS	2002	DBLP DOI BibTeX RDF
25	Vincent Limouzy, Fabien de Montgolfier, Michaël Rao	NLC-2 Graph Recognition and Isomorphism.	WG	2007	DBLP DOI BibTeX RDF
25	Stefan Szeider	On Fixed-Parameter Tractable Parameterizations of SAT.	SAT	2003	DBLP DOI BibTeX RDF
25	Christof Löding	Ground Tree Rewriting Graphs of Bounded Tree Width.	STACS	2002	DBLP DOI BibTeX RDF
22	Vasanth Krishna Namasivayam, Animesh Pathak, Viktor K. Prasanna	Scalable Parallel Implementation of Bayesian Network to Junction Tree Conversion for Exact Inference.	SBAC-PAD	2006	DBLP DOI BibTeX RDF
22	Narek Bojikian, Stefan Kratsch	Tight Algorithm for Connected Odd Cycle Transversal Parameterized by Clique-width.	CoRR	2024	DBLP DOI BibTeX RDF
22	Onur Çagirici, Petr Hlinený, Filip Pokrývka, Abhisekh Sankaran	Clique-width of point configurations.	J. Comb. Theory, Ser. B	2023	DBLP DOI BibTeX RDF
22	Robert Brignall, Daniel Cocks	A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width.	SIAM J. Discret. Math.	2023	DBLP DOI BibTeX RDF
22	Vera Chekan, Stefan Kratsch	Tight Algorithmic Applications of Clique-Width Generalizations.	CoRR	2023	DBLP DOI BibTeX RDF
22	Narek Bojikian, Stefan Kratsch	A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width.	CoRR	2023	DBLP DOI BibTeX RDF
22	Falko Hegerfeld, Stefan Kratsch	Tight algorithms for connectivity problems parameterized by clique-width.	CoRR	2023	DBLP DOI BibTeX RDF
22	Konrad K. Dabrowski, Tomás Masarík, Jana Novotná 0001, Daniël Paulusma, Pawel Rzazewski	Clique-width: Harnessing the power of atoms.	J. Graph Theory	2023	DBLP DOI BibTeX RDF
22	Falko Hegerfeld, Stefan Kratsch	Tight Algorithms for Connectivity Problems Parameterized by Clique-Width.	ESA	2023	DBLP DOI BibTeX RDF
22	Vera Chekan, Stefan Kratsch	Tight Algorithmic Applications of Clique-Width Generalizations.	MFCS	2023	DBLP DOI BibTeX RDF
22	Robert Brignall, Daniel Cocks	Uncountably Many Minimal Hereditary Classes of Graphs of Unbounded Clique-Width.	Electron. J. Comb.	2022	DBLP DOI BibTeX RDF
22	Guillaume Ducoffe	Maximum Matching in Almost Linear Time on Graphs of Bounded Clique-Width.	Algorithmica	2022	DBLP DOI BibTeX RDF
22	Guillaume Ducoffe	Optimal Centrality Computations Within Bounded Clique-Width Graphs.	Algorithmica	2022	DBLP DOI BibTeX RDF
22	Marco A. López Medina, J. Leonardo González-Ruiz, José Raymundo Marcial-Romero, José Antonio Hernández Servín	Computing the Clique-Width on Series-Parallel Graphs.	Computación y Sistemas	2022	DBLP BibTeX RDF
22	Narmina Baghirova, Carolina Lucía Gonzalez, David Schindl	Locally checkable problems in bounded clique-width graphs.	CoRR	2022	DBLP DOI BibTeX RDF
22	Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, Kirill Simonov	The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width.	CoRR	2022	DBLP DOI BibTeX RDF
22	Robert Brignall, Daniel Cocks	A framework for minimal hereditary classes of graphs of unbounded clique-width.	CoRR	2022	DBLP DOI BibTeX RDF
22	Irena Penev	On the structure and clique-width of ( 4 K 1 , C 4 , C 6 , C 7 ) -free graphs.	J. Graph Theory	2022	DBLP DOI BibTeX RDF
22	Narmina Baghirova, Carolina Lucía Gonzalez, Bernard Ries, David Schindl	Locally Checkable Problems Parameterized by Clique-Width.	ISAAC	2022	DBLP DOI BibTeX RDF
22	Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, Kirill Simonov	The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width.	ICALP	2022	DBLP DOI BibTeX RDF
22	Anuj Dawar, Abhisekh Sankaran	MSO Undecidability for Hereditary Classes of Unbounded Clique Width.	CSL	2022	DBLP DOI BibTeX RDF
22	Sriram Bhyravarapu, Tim A. Hartmann, Subrahmanyam Kalyanasundaram, I. Vinod Reddy	Conflict-Free Coloring: Graphs of Bounded Clique Width and Intersection Graphs.	CoRR	2021	DBLP BibTeX RDF
22	Chris Aronis	The Algorithmic Complexity of Tree-Clique Width.	CoRR	2021	DBLP BibTeX RDF
22	Aistis Atminas, Robert Brignall, Vadim V. Lozin, Juraj Stacho	Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs.	Discret. Appl. Math.	2021	DBLP DOI BibTeX RDF
22	Frank Gurski, Dominique Komander, Carolin Rehs	Acyclic Coloring Parameterized by Directed Clique-Width.	CALDAM	2021	DBLP DOI BibTeX RDF
22	J. Leonardo González-Ruiz, José Raymundo Marcial-Romero, José Antonio Hernández Servín, Guillermo De Ita	Approximate the Clique-Width of a Graph Using Shortest Paths.	MICAI (2)	2021	DBLP DOI BibTeX RDF
22	Sankardeep Chakraborty, Seungbum Jo, Kunihiko Sadakane, Srinivasa Rao Satti	Succinct Data Structures for Small Clique-Width Graphs.	DCC	2021	DBLP DOI BibTeX RDF
22	Lars Jaffke, Paloma T. Lima, Daniel Lokshtanov	b-Coloring Parameterized by Clique-Width.	STACS	2021	DBLP DOI BibTeX RDF
22	Sriram Bhyravarapu, Tim A. Hartmann, Subrahmanyam Kalyanasundaram, I. Vinod Reddy	Conflict-Free Coloring: Graphs of Bounded Clique Width and Intersection Graphs.	IWOCA	2021	DBLP DOI BibTeX RDF
22	Guillaume Ducoffe	Maximum Matching in Almost Linear Time on Graphs of Bounded Clique-Width.	IPEC	2021	DBLP DOI BibTeX RDF
22	Guillaume Ducoffe	Optimal Centrality Computations Within Bounded Clique-Width Graphs.	IPEC	2021	DBLP DOI BibTeX RDF