Linear-time algorithms for graphs of bounded rankwidth: a fresh look using game theory (extended abstract)

DOI10.1007/978-3-642-20877-5_49MaRDI QIDQ3010429zbMATH OpenOpenAlexFDO

Authors Alexander Langer, Somnath Sikdar, Peter Rossmanith

Publication date 1 July 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-20877-5_49

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Games involving graphs (91A43)

Recommendations

• Courcelle's theorem -- a game-theoretic approach
• A Practical Approach to Courcelle's Theorem
• Automata approach to graphs of bounded rank-width
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• Vertex-minors, monadic second-order logic, and a conjecture by Seese

Cites work

• scientific article; zbMATH DE number 3761989 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 3399180 (Why is no real title available?)
• Approximating clique-width and branch-width
• Courcelle's theorem -- a game-theoretic approach
• Easy problems for tree-decomposable graphs
• Finding Branch-Decompositions and Rank-Decompositions
• Graph Operations Characterizing Rank-Width and Balanced Graph Expressions
• Improving Efficiency and Simplicity of Tor Circuit Establishment and Hidden Services
• Linear time solvable optimization problems on graphs of bounded clique-width
• Modest theory of short chains. I
• Monadic second-order definable graph transductions: a survey
• Monadic second-order evaluations on tree-decomposable graphs
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• The first order properties of products of algebraic systems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(9)

• Practical algorithms for MSO model-checking on tree-decomposable graphs
• Courcelle's theorem -- a game-theoretic approach
• On complexities of minus domination
• Automata approach to graphs of bounded rank-width
• Transforming graph states using single-qubit operations
• Confronting intractability via parameters
• On complexities of minus domination
• On \textsf{NC} algorithms for problems on bounded rank-width graphs
• Classes of graphs with low complexity: the case of classes with bounded linear rankwidth

This page was built for publication: Linear-time algorithms for graphs of bounded rankwidth: a fresh look using game theory (extended abstract)

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