Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory

DOI10.1007/978-3-642-20877-5_49zbMath1331.68111MaRDI QIDQ3010429

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

68Q25: Analysis of algorithms and problem complexity

91A43: Games involving graphs

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Transforming graph states using single-qubit operations, Confronting intractability via parameters, Practical algorithms for MSO model-checking on tree-decomposable graphs, On complexities of minus domination, On Complexities of Minus Domination

Cites Work

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