On Some Combinatorial Problems in Cographs
| Autor: | Harshita Kona, N. Sadagopan |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
FOS: Computer and information sciences
Spanning tree Optimization problem Computer science Parse tree 01 natural sciences Hamiltonian path Longest path problem 010305 fluids & plasmas Vertex (geometry) Dynamic programming Combinatorics symbols.namesake Computer Science::Discrete Mathematics 0103 physical sciences Computer Science - Data Structures and Algorithms symbols Data Structures and Algorithms (cs.DS) Cograph 010306 general physics Computer Science::Data Structures and Algorithms MathematicsofComputing_DISCRETEMATHEMATICS |
| Popis: | The family of graphs that can be constructed from isolated vertices by disjoint union and graph join operations are called cographs. These graphs can be represented in a tree-like representation termed parse tree or cotree. In this paper, we study some popular combinatorial problems restricted to cographs. We first present a structural characterization of minimal vertex separators in cographs. Further, we show that listing all minimal vertex separators and the complexity of some constrained vertex separators are polynomial-time solvable in cographs. We propose polynomial-time algorithms for connectivity augmentation problems and its variants in cographs, preserving the cograph property. Finally, using the dynamic programming paradigm, we present a generic framework to solve classical optimization problems such as the longest path, the Steiner path and the minimum leaf spanning tree problems restricted to cographs, our framework yields polynomial-time algorithms for all three problems. 21 pages, 4 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|