Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory
From MaRDI portal
Publication:3010429
DOI10.1007/978-3-642-20877-5_49zbMath1331.68111OpenAlexW1651767865MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (5)
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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory