scientific article; zbMATH DE number 7053307
From MaRDI portal
Publication:5743428
zbMath1423.68342MaRDI QIDQ5743428
Marcin Kaminski, Naomi Nishimura
Publication date: 10 May 2019
Full work available at URL: https://dl.acm.org/citation.cfm?id=2095171
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (4)
Finding a shortest even hole in polynomial time ⋮ Combing a Linkage in an Annulus ⋮ Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear algorithm for the group path problem on chordal graphs
- Efficient reduction for path problems on circular-arc graphs
- A new property of critical imperfect graphs and some consequences
- On the complexity of testing for odd holes and induced odd paths
- Quickly excluding a planar graph
- Path parity and perfection
- A polynomial algorithm for the parity path problem on perfectly orientable graphs
- The parity path problem on some subclasses of perfect graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The even-path problem for graphs and digraphs
- The Induced Disjoint Paths Problem
- Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
- Transformations which Preserve Perfectness and H-Perfectness of Graphs
- Modularity of cycles and paths in graphs
- Recognizing Perfect 2-Split Graphs
- Finding an Even Simple Path in a Directed Planar Graph
- The Graph Minor Algorithm with Parity Conditions
- The Strong Perfect Graph Conjecture for Planar Graphs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Finding Induced Paths of Given Parity in Claw-Free Graphs
- Recognizing planar strict quasi-parity graphs
This page was built for publication:
