Name
Abstract | ||
|---|---|---|
We study the complexity of several of the classical graph decision problems in the setting of bounded cutwidth and how imposing planarity affects the complexity. We show that for 2-coloring, for bipartite perfect matching, and for several variants of disjoint paths, the straightforward NC1 upper bound may be improved to AC(0) [2], ACC(0), and AC(0) respectively for bounded planar cutwidth graphs. We obtain our upper bounds using the characterization of these circuit classes in tems of finite monoids due to Barrington and Therien. On the other hand we show that 3-coloring and Hamilton cycle remain hard for NC1 under projection reductions, analogous to the NP-completeness for general planar graphs. We also show that 2-coloring and (non-bipartite) perfect matching are hard under projection reductions for certain subclasses of AC(0) [2]. In particular this shows that our bounds for 2-coloring are quite close. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-662-44465-8_29 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Planarity testing,Disjoint sets,Graph property,Upper and lower bounds,Computer science,Bipartite graph,Matching (graph theory),Planar graph,Bounded function | Conference | 8635 |
ISSN | Citations | PageRank |
0302-9743 | 1 | 0.35 |
References | Authors | |
12 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kristoffer Arnsfelt Hansen | 1 | 1 | 0.35 |
| Balagopal Komarath | 2 | 4 | 3.16 |
| Jayalal M. N. Sarma | 3 | 17 | 9.16 |
| Sven Skyum | 4 | 1 | 0.35 |
| Navid Talebanfard | 5 | 6 | 5.55 |