Directed NLC-width

DOI10.1016/j.tcs.2015.11.003zbMath1334.05166OpenAlexW2195002222MaRDI QIDQ906393

Frank Gurski, Eda Yilmaz, Egon Wanke

Publication date: 21 January 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.11.003

zbMATH Keywords

digraphsdirected clique-widthdirected NLC-width

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Directed graphs (digraphs), tournaments (05C20)

Related Items

Computing directed Steiner path covers, Acyclic coloring parameterized by directed clique-width, Directed width parameters on semicomplete digraphs, Efficient parameterized algorithms for computing all-pairs shortest paths, Twin-distance-hereditary digraphs, Solutions for subset sum problems with special digraph constraints, How to compute digraph width measures on directed co-graphs, Computing Directed Steiner Path Covers for Directed Co-graphs (Extended Abstract), Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs, Efficient computation of the oriented chromatic number of recursively defined digraphs, The behavior of clique-width under graph operations and graph transformations, Oriented coloring on recursively defined digraphs, On characterizations for subclasses of directed co-graphs, Comparing linear width parameters for directed graphs, Digraphs of Bounded Width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• The dag-width of directed graphs
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• Digraph measures: Kelly decompositions, games, and orderings
• Clique-width of graphs defined by one-vertex extensions
• Every 7-regular digraph contains an even cycle
• S-functions for graphs
• \(k\)-NLC graphs and polynomial algorithms
• Directed tree-width
• Edge dominating set and colorings on graphs with fixed clique-width
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Polynomial algorithms for protein similarity search for restricted mRNA structures
• The rank-width of edge-coloured graphs
• Digraph width measures in parameterized algorithmics
• Line graphs of bounded clique-width
• Parametrized complexity theory.
• Approximating clique-width and branch-width
• Fully dynamic recognition algorithm and certificate for directed cographs
• Vertex disjoint paths on clique-width bounded graphs
• Directed tree-width examples
• Model-Checking by Infinite Fly-Automata
• Are There Any Good Digraph Width Measures?
• Clique-Width is NP-Complete
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• A complete axiomatisation for the inclusion of series-parallel partial orders
• Digraphs