The fastest itinerary in time-dependent decentralized travel information systemsSpringer Science and Business Media LLC - Tập 12 - Trang 167-185 - 2006
Jinchang Wang, Thomas Kämpke
A travel information system (TIS) provides customers with information about transportation, transfers, and routings. A decentralized TIS is composed of autonomous subsystems and a central computer, where local subsystems have full control of their data and there is not a complete database in the central computer about the entire TIS. The transportation vehicles are scheduled. A travel itinerary fr...... hiện toàn bộ
Spanning tree of a multiple graphSpringer Science and Business Media LLC - Tập 43 - Trang 850-869 - 2021
Alexander V. Smirnov
We study undirected multiple graphs of any natural multiplicity
$$k>1$$
. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is a union of k linked edges, which connect 2 or
...... hiện toàn bộ
On list r-hued coloring of planar graphsSpringer Science and Business Media LLC - Tập 34 - Trang 874-890 - 2017
Haiyang Zhu, Sheng Chen, Lianying Miao, Xinzhong Lv
A list
assignment of G is a function L that assigns to each vertex
$$v\in V(G)$$
a list L(v) of available colors. Let r be a positive integer. For a given list assignment L of G, an (L, r)-coloring of G is a proper colori...... hiện toàn bộ
Restrained domination in cubic graphsSpringer Science and Business Media LLC - Tập 22 - Trang 166-179 - 2010
Johannes H. Hattingh, Ernst J. Joubert
Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set if every vertex in V−S is adjacent to a vertex in S and to a vertex in V−S. The restrained domination number of G, denoted γ
r
(G), is the smallest cardinality of a restrained dominating set of G. A graph G is said to be cubic if every vertex has degree three. In this paper, ...... hiện toàn bộ
Approximation and Exact Algorithms for Constructing Minimum Ultrametric Trees from Distance MatricesSpringer Science and Business Media LLC - Tập 3 - Trang 199-211 - 1999
Bang Ye Wu, Kun-Mao Chao, Chuan Yi Tang
An edge-weighted tree is called ultrametric if the distances from the root to all the leaves in the tree are equal. For an n by n distance matrix M, the minimum ultrametric tree for M is an ultrametric tree T = (V, E, w) with leaf set {1,..., n} such that dT(i, j) ≥ M[i, j] for all i, j and
$$\sum {_{e \in E} w(e)}$$
...... hiện toàn bộ
An ant colony optimization approach for the proportionate multiprocessor open shopSpringer Science and Business Media LLC - Tập 43 - Trang 785-817 - 2021
Zeynep Adak, Mahmure Övül Arıoğlu, Serol Bulkan
Multiprocessor open shop makes a generalization to classical open shop by allowing parallel machines for the same task. Scheduling of this shop environment to minimize the makespan is a strongly NP-Hard problem. Despite its wide application areas in industry, the research in the field is still limited. In this paper, the proportionate case is considered where a task requires a fixed processing tim...... hiện toàn bộ
Ant Colony System for a Dynamic Vehicle Routing ProblemSpringer Science and Business Media LLC - Tập 10 - Trang 327-343 - 2005
R. Montemanni, L. M. Gambardella, A. E. Rizzoli, A. V. Donati
An aboundant literature on vehicle routing problems is available. However, most of the work deals with static problems, where all data are known in advance, i.e. before the optimization has started. The technological advances of the last few years give rise to a new class of problems, namely the dynamic vehicle routing problems, where new orders are received as time progresses and must be dynamica...... hiện toàn bộ
On maximum $$P_3$$ -packing in claw-free subcubic graphsSpringer Science and Business Media LLC - Tập 41 - Trang 694-709 - 2021
Wenying Xi, Wensong Lin
Let
$$P_3$$
denote the path on three vertices. A
$$P_3$$
-packing of a given graph G is a collection of vertex-disjoint subgraphs of G in which each subgraph is isomorphic to
...... hiện toàn bộ
Fast searching on cactus graphsSpringer Science and Business Media LLC - - 2023
Yuan Xue, Boting Yang, Sandra Zilles, Lusheng Wang
The problem of finding the fast search number of a graph is NP-complete. It is challenging even when the graph has very small treewidth. However, it can be much easier to find an optimal fast search strategy for smaller subgraphs with special properties. This observation motivates us to establish relationships between optimal fast search strategies for a graph and its subgraphs although fast searc...... hiện toàn bộ
A DC programming approach for solving a centralized group key management problemSpringer Science and Business Media LLC - Tập 44 - Trang 3165-3193 - 2022
Hoai An Le Thi, Thi Tuyet Trinh Nguyen, Hoang Phuc Hau Luu
A single trusted entity known as a Key Server is in charge of key generation, distribution, and management in centralized key management schemes. To prevent eavesdropping and protect the exchange content, a group key is used to encrypt the group communication. This management mechanism is typically based on a binary tree structure. When the membership of a group changes dynamically, the group key ...... hiện toàn bộ