Minimizing Branching Vertices in Distance-Preserving Subgraphs
| Autor: | Jaikumar Radhakrishnan, Kshitij Gajjar |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Interval graph
0102 computer and information sciences 02 engineering and technology 01 natural sciences Combinatorics Branching (linguistics) 010201 computation theory & mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY 020204 information systems 0202 electrical engineering electronic engineering information engineering Graph (abstract data type) Undirected graph Time complexity MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Computer Science – Theory and Applications ISBN: 9783030199548 CSR |
| DOI: | 10.1007/978-3-030-19955-5_12 |
| Popis: | It is \(\textsf {NP}\)-hard to determine the minimum number of branching vertices needed in a single-source distance-preserving subgraph of an undirected graph. We show that this problem can be solved in polynomial time if the input graph is an interval graph. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|