Top

Journal of Applied and Industrial Mathematics

Published in:

01-11-2021

A Win/Win Algorithm for the \((k+1) \)-LST/\(k \)-Pathwidth Problem

Authors: A. G. Klyuchikov, M. N. Vyalyi

Published in: Journal of Applied and Industrial Mathematics | Issue 4/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We describe a Win/Win algorithm that produces in time polynomial in the size of a graph \(G \) and a given parameter \(k \) either a spanning tree with at least \(k+1 \) leaves or a path decomposition of width at most \(k \). This algorithm is optimal due to the path decomposition theorem.

previous article Construction of Solutions to a Boundary Value Problem with Singularity for a Nonlinear Parabolic System

next article The Generalized Derivative and Its Use in the Analysis of the Microstructure of a Heterogeneous Medium

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

D. Bienstock, N. Robertson, P. D. Seymour, and R. Thomas, “Quickly Excluding a Forest,” J. Comb. Theory, Ser. B, 52, 274–283 (1991).MathSciNetCrossRef

R. J. Douglas, “NP-Completeness and Degree Restricted Spanning Trees,” Discrete Math. 105 (1-3), 41–47 (1992).MathSciNetCrossRef

T. Kashiwabara and T. Fujisawa, “NP-Completeness of the Problem of Finding a Minimum-Clique-Number Interval Graph Containing a Given Graph as a subgraph,” in Proceedings. 1979 International Symposium on Circuits and Systems (Tokyo, Japan, July 17–19, 1979) (IEEE, New York, 1979), pp. 657–660.

H. L. Bodlaender, E. D. Demaine, M. R. Fellows, et al. Open Problems in Parameterized and Exact Computation—IWPEC 2008 . Techn. Rep. UU–CS–2008–017 (Utrecht Univ., Utrecht, 2008). Available at http://www.cs.uu.nl/research/techreps/repo/CS-2008/2008-017.pdf (accessed Aug. 3, 2021).

R. Diestel, “Graph Minors I: A Short Proof of the Path-Width Theorem,” Comb. Prob. Comput. 4 (1), 27–30 (1995).CrossRef

Title: A Win/Win Algorithm for the -LST/-Pathwidth Problem
Authors: A. G. Klyuchikov
M. N. Vyalyi
Publication date: 01-11-2021
Publisher: Pleiades Publishing
Published in: Journal of Applied and Industrial Mathematics / Issue 4/2021
Print ISSN: 1990-4789
Electronic ISSN: 1990-4797
DOI: https://doi.org/10.1134/S1990478921040062

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Other articles of this Issue 4/2021

Asymptotic Enumeration of Labeled Series-Parallel -Cyclic Bridgeless Graphs

A Robust Neural Network with Simple Architecture

Modeling the Isotropic Growth of an Incompressible Neo-Hookean Material

A Mathematical Model of a Reproduction System for Multifactor Dynamic Balances of Production and Consumption

The Generalized Derivative and Its Use in the Analysis of the Microstructure of a Heterogeneous Medium

Construction of Solutions to a Boundary Value Problem with Singularity for a Nonlinear Parabolic System

Premium Partners