Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs |
| |
| Institution: | 1. Department of Geosciences, Smith College, 44 College Lane, Northampton, MA 01063, USA;2. Department of Earth and Planetary Sciences, Harvard University, 20 Oxford Street, Cambridge, MA 02138, USA;1. Department of Earth and Environmental Sciences, University of Rochester, Rochester, NY 14627, USA;2. Department of Oceanography, Texas A&M University, College Station, TX 77843, USA;3. Department of Earth and Planetary Sciences, University of California, Santa Cruz, CA 95064, USA;4. Department of Geological Sciences, University of Alabama, Tuscaloosa, AL 35487, USA;1. School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore;2. Electrical & Electronic Engineering, Newcastle University, United Kingdom;3. School of Automation, Wuhan University of Technology, China;1. Centre for Power and Energy Systems (CPES), INESC TEC, Porto, Portugal;2. Faculty of Engineering of University of Porto (FEUP), Porto, Portugal;1. Centro de Investigación y Estudios de Posgrado, Engineering Department, Universidad Autónoma de San Luis Potosí, Av. Dr. Manuel Nava 8, Zona Universitaria, 78290 San Luis Potosí, Mexico;2. Electrical Engineering Department, Universidad de Concepción, Edmundo Larenas 219, Concepción, Chile |
| |
| Abstract: | We present subexponential parameterized algorithms on planar graphs for a family of problems that consist in, given a graph G, finding a connected (induced) subgraph H with bounded maximum degree, while maximising the number of edges (or vertices) of H. These problems are natural generalisations of Longest Path. Our approach uses bidimensionality theory combined with novel dynamic programming techniques over branch decompositions of the input graph. These techniques can be applied to a more general family of problems that deal with finding connected subgraphs under certain degree constraints. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
