Digraphs of bounded elimination width

DOI10.1016/J.DAM.2013.05.005MaRDI QIDQ2442210zbMATH OpenOpenAlexFDO

Authors Henning Fernau, Daniel Meister

Publication date 2 April 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2013.05.005

zbMATH Keywords

characterisationscops-and-robber gamesdigraphsperfect elimination

Mathematics Subject Classification ID

Vertex degrees (05C07) Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

Recommendations

• Digraph measures: Kelly decompositions, games, and orderings
• Digraph measures: Kelly decompositions, games, and orderings
• Recognizing digraphs of Kelly-width 2
• Characterization and Recognition of Digraphs of Bounded Kelly-width
• On digraph width measures in parameterized algorithmics

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Algorithmic Aspects of Vertex Elimination on Directed Graphs
• Approximating clique-width and branch-width
• Are there any good digraph width measures?
• Chordal digraphs
• Complexity of Finding Embeddings in a k-Tree
• Computing the Minimum Fill-In is NP-Complete
• DAG-width
• DAG-Width and Parity Games
• Digraph Decompositions and Monotonicity in Digraph Searching
• Digraph measures: Kelly decompositions, games, and orderings
• Directed tree-width
• Fugitive-search games on graphs and related parameters
• Linear time solvable optimization problems on graphs of bounded clique-width
• Recognizing digraphs of Kelly-width 2
• The dag-width of directed graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Toward Characterization of Perfect Elimination Digraphs

Cited in

(9)

• Digraph measures: Kelly decompositions, games, and orderings
• Digraphs of bounded width
• Characterization and Recognition of Digraphs of Bounded Kelly-width
• Synchronizing series-parallel deterministic finite automata with loops and related problems
• Digraph coloring and distance to acyclicity
• Digraph coloring and distance to acyclicity
• Directed elimination games
• Digraph measures: Kelly decompositions, games, and orderings
• Recognizing digraphs of Kelly-width 2

This page was built for publication: Digraphs of bounded elimination width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2442210)