Wyniki wyszukiwania - Biblioteka Nauki

Ten serwis zostanie wyłączony 2025-02-11.

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

Znaleziono wyników: 7

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: longest path

Sortuj według:

Ogranicz wyniki do:

On the longest path in a recursively partitionable graph

100%

Bensmail J.

Opuscula Mathematica

2013

tom Vol. 33, no. 4

631--640

A connected graph G with order n ≥ 1 is said to be recursively arbitrarily partitionable (R-AP for short) if either it is isomorphic to K1, or for every sequence (n1, . . . , np) of positive integers summing up to n there exists a partition (V1, . . . , Vp) of V (G) such that each Vi induces a connected R-AP subgraph of G on ni vertices. Since previous investigations, it is believed that a R-AP graph should be “almost traceable” somehow. We first show that the longest path of a R-AP graph on n vertices is not constantly lower than n for every n. This is done by exhibiting a graph family C such that, for every positive constant c ≥ 1, there is a R-AP graph in C that has arbitrary order n and whose longest path has order n−c. We then investigate the largest positive constant c’ < 1 such that every R-AP graph on n vertices has its longest path passing through n • c’ vertices. In particular, we show that c’ ≥ 2/3 . This result holds for R-AP graphs with arbitrary connectivity.

Interactive knapsacks

80%

Aho I.

Fundamenta Informaticae

2000

tom Vol. 44, Nr 1,2

1-23

The interactive knapsack problems are generalizations of the classical knapsack problem. Three different new NP-complete problems, interactive knapsack heuristic decision problem (IKHD), interactive knapsack decision problem (IKD) and multidimensional cloned knapsack decision problem (MDCS), are presented for the interactive knapsack models. IKD and MDCS are shown to be strongly NP-complete. By using interactive knapsacks we can model many planning and scheduling problems in an innovative way. Possible application areas include electricity management, single and multiprocessor scheduling, and packing and tiling problems. As a by-product we show that the longest weight-constrained path problem is NP-complete.

New Polynomial-time Instances to Various Knapsack-type Problems

80%

Aho I.

Fundamenta Informaticae

2002

tom Vol. 53, nr 3,4

199-228

We describe a special case of the interactive knapsack optimization problem (motivated by the load clipping problem) solvable in polynomial time. Given an instance parameterized by k, the solution can be found in polynomial time, where the polynomial has degree k. In the interactive knapsack problem, k is connected to the length induced by an item. A similar construction solves a special case of the 0-1 multi-dimensional knapsack and the 0-1 linear integer programming problems in polynomial time. In these problems the parameter determines the width of the restriction matrix, which is a band matrix. We extend the 0-1 multi-dimensional knapsack solution to 0-n multi-dimensional knapsack problems (and to 0-n IP problems). Our algorithms are based on the (resource bounded) shortest path search: we represent restrictions efficiently in a form of a graph such that each feasible solution has a path between given source and target vertices.

Independent transversals of longest paths in locally semicomplete and locally transitive digraphs

80%

Galeana-Sánchez H. , Gómez R. , Montellano-Ballesteros J.

Discussiones Mathematicae Graph Theory

2009

tom 29

nr 3

469-480

We present several results concerning the Laborde-Payan-Xuang conjecture stating that in every digraph there exists an independent set of vertices intersecting every longest path. The digraphs we consider are defined in terms of local semicompleteness and local transitivity. We also look at oriented graphs for which the length of a longest path does not exceed 4.

Independent Detour Transversals in 3-Deficient Digraphs

70%

van Aardt S. , Frick M. , Singleton J.

Discussiones Mathematicae Graph Theory

2013

tom 33

nr 2

261-275

In 1982 Laborde, Payan and Xuong [Independent sets and longest directed paths in digraphs, in: Graphs and other combinatorial topics (Prague, 1982) 173-177 (Teubner-Texte Math., 59 1983)] conjectured that every digraph has an independent detour transversal (IDT), i.e. an independent set which intersects every longest path. Havet [Stable set meeting every longest path, Discrete Math. 289 (2004) 169-173] showed that the conjecture holds for digraphs with independence number two. A digraph is p-deficient if its order is exactly p more than the order of its longest paths. It follows easily from Havet’s result that for p = 1, 2 every p-deficient digraph has an independent detour transversal. This paper explores the existence of independent detour transversals in 3-deficient digraphs.

The directed path partition conjecture

70%

Frick M. , van Aardt S. , Dlamini G. , Dunbar J. , Oellermann O.

Discussiones Mathematicae Graph Theory

2005

tom 25

nr 3

331-343

The Directed Path Partition Conjecture is the following: If D is a digraph that contains no path with more than λ vertices then, for every pair (a,b) of positive integers with λ = a+b, there exists a vertex partition (A,B) of D such that no path in D⟨A⟩ has more than a vertices and no path in D⟨B⟩ has more than b vertices. We develop methods for finding the desired partitions for various classes of digraphs.

Detour chromatic numbers

60%

Frick M. , Bullock F.

Discussiones Mathematicae Graph Theory

2001

tom 21

nr 2

283-291

The nth detour chromatic number, χₙ(G) of a graph G is the minimum number of colours required to colour the vertices of G such that no path with more than n vertices is monocoloured. The number of vertices in a longest path of G is denoted by τ( G). We conjecture that χₙ(G) ≤ ⎡(τ(G))/n⎤ for every graph G and every n ≥ 1 and we prove results that support the conjecture. We also present some sufficient conditions for a graph to have nth chromatic number at most 2.