Search results for "vertex-connectivity"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
91	Weifa Liang, Richard P. Brent, Hong Shen	Fully Dynamic Maintenance of k-Connectivity in Parallel.	IEEE Trans. Parallel Distributed Syst.	2001	DBLP DOI BibTeX RDF	2-edge/vertex connectivity, 3-edge/vertex connectivity, parallel algorithm design and analysis, dynamic data structures, graph problems, NC algorithms
72	David Eppstein, Zvi Galil, Giuseppe F. Italiano, Amnon Nissenzweig	Sparsification - a technique for speeding up dynamic graph algorithms.	J. ACM	1997	DBLP DOI BibTeX RDF	edge and vertex connectivity, minimum spanning trees, dynamic graph algorithms
71	Tanmoy Chakraborty 0001, Julia Chuzhoy, Sanjeev Khanna	Network design for vertex connectivity.	STOC	2008	DBLP DOI BibTeX RDF	approximation algorithms, network design, hardness of approximation, vertex connectivity
67	Yuichi Yoshida, Hiro Ito	Property Testing on k-Vertex-Connectivity of Graphs.	ICALP (1)	2008	DBLP DOI BibTeX RDF
59	Amos Korman	Labeling Schemes for Vertex Connectivity.	ICALP	2007	DBLP DOI BibTeX RDF	Graph algorithms, labeling schemes, vertex-connectivity
57	Harold N. Gabow	Using expander graphs to find vertex connectivity.	J. ACM	2006	DBLP DOI BibTeX RDF	graphs, Expander graphs, vertex connectivity
57	Julia Chuzhoy, Sanjeev Khanna	Algorithms for Single-Source Vertex Connectivity.	FOCS	2008	DBLP DOI BibTeX RDF
53	R. Ravi 0001, David P. Williamson	Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems.	Algorithmica	2002	DBLP DOI BibTeX RDF
50	Toshimasa Ishii	Greedy Approximation for Source Location Problem with Vertex-Connectivity Requirements in Undirected Graphs.	ISAAC	2007	DBLP DOI BibTeX RDF
48	Guy Kortsarz, Robert Krauthgamer, James R. Lee	Hardness of Approximation for Vertex-Connectivity Network-Design Problems.	APPROX	2002	DBLP DOI BibTeX RDF
47	Chandra Chekuri, Nitish Korula	A Graph Reduction Step Preserving Element-Connectivity and Applications.	ICALP (1)	2009	DBLP DOI BibTeX RDF
43	Bill Jackson, Tibor Jordán	Independence Free Graphs and Vertex Connectivity Augmentation.	IPCO	2001	DBLP DOI BibTeX RDF
43	Lisa Fleischer	A 2-Approximation for Minimum Cost {0, 1, 2} Vertex Connectivity.	IPCO	2001	DBLP DOI BibTeX RDF
41	Michal Katz, Nir A. Katz, Amos Korman, David Peleg	Labeling schemes for flow and connectivity.	SODA	2002	DBLP BibTeX RDF
40	Ning Li 0014, Jennifer C. Hou	FLSS: a fault-tolerant topology control algorithm for wireless networks.	MobiCom	2004	DBLP DOI BibTeX RDF	k-vertex, fault tolerance, wireless networks, connectivity, topology control, energy management
40	Julia Chuzhoy, Sanjeev Khanna	An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design.	FOCS	2009	DBLP DOI BibTeX RDF	vertex-connectivity, survivable network design
40	László A. Végh, András A. Benczúr	Primal-dual approach for directed vertex connectivity augmentation and generalizations.	ACM Trans. Algorithms	2008	DBLP DOI BibTeX RDF	Vertex connectivity augmentation, combinatorial algorithm
40	Harold N. Gabow	Using Expander Graphs to Find Vertex Connectivity.	FOCS	2000	DBLP DOI BibTeX RDF	nesting properties, separation triples, computational complexity, complexity, graph theory, expander graphs, undirected graph, digraph, time bound, vertex connectivity
40	Monika Rauch Henzinger, Satish Rao, Harold N. Gabow	Computing Vertex Connectivity: New Bounds from Old Techniques.	FOCS	1996	DBLP DOI BibTeX RDF	smallest number of vertices, preflow push algorithm, computational geometry, deterministic algorithm, digraph, error probability, vertex connectivity
39	Joseph Cheriyan, John H. Reif	Directed s-t Bumberings, Rubber Bands, and Testing Digraph k-Vertex Connectivity.	SODA	1992	DBLP BibTeX RDF
37	L. Sunil Chandran	Edge Connectivity vs Vertex Connectivity in Chordal Graphs.	COCOON	2001	DBLP DOI BibTeX RDF
35	Mariko Sakashita, Kazuhisa Makino, Satoru Fujishige	Minimum Cost Source Location Problems with Flow Requirements.	Algorithmica	2008	DBLP DOI BibTeX RDF	Approximation algorithm, Combinatorial optimization, Connectivity, Location problem
35	Yuk Hei Chan, Wai Shing Fung, Lap Chi Lau, Chun Kong Yung	Degree Bounded Network Design with Metric Costs.	FOCS	2008	DBLP DOI BibTeX RDF
33	Monika Rauch Henzinger	A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity.	J. Algorithms	1997	DBLP DOI BibTeX RDF
33	Tsan-sheng Hsu	Undirected Vertex-Connectivity Structure and Smallest Four-Vertex-Connectivity Augmentation.	ISAAC	1995	DBLP DOI BibTeX RDF
33	Marcelo M. de Azevedo, Nader Bagherzadeh, Shahram Latifi	Fault-diameter of the star-connected cycles interconnection network.	HICSS (2)	1995	DBLP DOI BibTeX RDF	star-connected cycles interconnection network, maximum diameter, fault-free, fixed constant, fault tolerance, reliability, graph theory, parallel architectures, fault tolerant computing, graph, multiprocessor interconnection networks, vertex connectivity, fault-diameter
31	Joseph Cheriyan, Santosh S. Vempala, Adrian Vetta	Network Design Via Iterative Rounding Of Setpair Relaxations.	Comb.	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 68W25, 90C27, 68R10, 90C35, 05C40, 90B10
31	Ning Li 0014, Jennifer C. Hou	Localized Fault-Tolerant Topology Control in Wireless Ad Hoc Networks.	IEEE Trans. Parallel Distributed Syst.	2006	DBLP DOI BibTeX RDF	fault tolerance, wireless ad hoc networks, topology control, localized algorithms, Algorithm design and analysis
31	L. Sunil Chandran, N. S. Narayanaswamy	On the Arrangement of Cliques in Chordal Graphs with Respect to the Cuts.	COCOON	2004	DBLP DOI BibTeX RDF
30	Pei-Chi Huang, Hsin-Wen Wei, Yen-Chiu Chen, Ming-Yang Kao, Wei-Kuan Shih, Tsan-sheng Hsu	Two-Vertex Connectivity Augmentations for Graphs with a Partition Constraint (Extended Abstract).	ISAAC	2009	DBLP DOI BibTeX RDF
30	Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki	K-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph.	ISAAC	1998	DBLP DOI BibTeX RDF
27	Weifa Liang, George Havas	NC Approximation Algorithms for 2-Connectivity Augmentation in a Graph.	Euro-Par	1997	DBLP DOI BibTeX RDF
26	Jianhui Zhang, Jiming Chen 0001, Yu Wang 0003, Yang Xiao 0001, Youxian Sun	A simple algorithm for fault-tolerant topology control in wireless sensor network.	PIMRC	2008	DBLP DOI BibTeX RDF
26	Samir Khuller, Uzi Vishkin	Biconnectivity Approximations and Graph Carvings.	J. ACM	1994	DBLP DOI BibTeX RDF	sparse subgraphs, connectivity, biconnectivity
26	Mariko Sakashita, Kazuhisa Makino, Satoru Fujishige	Minimum Cost Source Location Problems with Flow Requirements.	LATIN	2006	DBLP DOI BibTeX RDF
26	Keren Censor-Hillel, Mohsen Ghaffari 0001, George Giakkoupis, Bernhard Haeupler, Fabian Kuhn	Tight Bounds on Vertex Connectivity Under Vertex Sampling.	SODA	2015	DBLP DOI BibTeX RDF
26	Loukas Georgiadis	Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs.	ICALP (1)	2010	DBLP DOI BibTeX RDF
25	Matthias Kriesell	A Survey on Contractible Edges in Graphs of a Prescribed Vertex Connectivity.	Graphs Comb.	2002	DBLP DOI BibTeX RDF
25	R. Ravi 0001, David P. Williamson	Erratum: an approximation algorithm for minimum-cost vertex-connectivity problems.	SODA	2002	DBLP BibTeX RDF
24	Christos A. Athanasiadis	On the Graph Connectivity of Skeleta of Convex Polytopes.	Discret. Comput. Geom.	2009	DBLP DOI BibTeX RDF	Balinski’s theorem, Incidence graph, Skeleton, Convex polytope, Cell complex, Vertex connectivity
24	Weiping Shang, F. Frances Yao, Peng-Jun Wan, Xiaodong Hu 0001	Algorithms for Minimum m -Connected k -Dominating Set Problem.	COCOA	2007	DBLP DOI BibTeX RDF	k-vertex connectivity, wireless sensor networks, approximation algorithm, Connected dominating set
24	Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki	Augmenting a (k-1)-Vertex-Connected Multigraph l-Edge-Connected and k-Vertex-Connected Multigraph.	Algorithmica	2006	DBLP DOI BibTeX RDF	Undirected multigraph, Graph augmentation, Deterministic algorithm, Edge-connectivity, Vertex-connectivity, Polynomial time approximation algorithm
24	Shahram Latifi, Manju V. Hegde, Morteza Naraghi-Pour	Conditional Connectivity Measures for Large Multiprocessor Systems.	IEEE Trans. Computers	1994	DBLP DOI BibTeX RDF	conditional connectivity, large regular graphs, n-dimensional cube, fault tolerant computing, hypercube, multiprocessing systems, multiprocessor systems, hypercube networks, vertex connectivity
24	Kemal Efe	A Variation on the Hypercube with Lower Diameter.	IEEE Trans. Computers	1991	DBLP DOI BibTeX RDF	distributed-memory parallel computer architectures, large vertex connectivity, link complexity, routing, parallel architectures, hypercube, regularity, hypercube networks, broadcasting algorithms, interconnection structure
24	Samir Khuller, Baruch Schieber	Efficient Parallel Algorithms for Testing Connectivity and Finding Disjoint s-t Paths in Graphs (Extended Summary)	FOCS	1989	DBLP DOI BibTeX RDF	k-edge disjoint paths, testing connectivity, disjoint s-t paths, optimal speedup algorithm, k-vertex connectivity, parallel algorithms, graphs, CRCW PRAM
23	Clarianne Luciola de A. V. M. Lucas, Renata R. Del-Vecchio, Maria Aguieiras A. de Freitas, Joice S. do Nascimento	Relationships between algebraic connectivity and vertex connectivity.	Comput. Appl. Math.	2022	DBLP DOI BibTeX RDF
23	Jun Liang 0002, Meixin Du, Ruihua Nie, Zhihao Liang, Zheng Li	Distributed Algorithms for Cyclic Edge Connectivity and Cyclic Vertex Connectivity of Cubic Graphs.	ICDSP	2020	DBLP DOI BibTeX RDF
23	Abusayeed Saifullah	2-Edge-Connectivity and 2-Vertex-Connectivity of an Asynchronous Distributed Network.	CoRR	2019	DBLP BibTeX RDF
23	Hiro Ito, Motoyasu Ito, Yuichiro Itatsu, Kazuhiro Nakai, Hideyuki Uehara, Mitsuo Yokoyama	Source location problems considering vertex-connectivity and edge-connectivity simultaneously.	Networks	2002	DBLP DOI BibTeX RDF
23	Zvi Galil, Giuseppe F. Italiano	Reducing edge connectivity to vertex connectivity.	SIGACT News	1991	DBLP DOI BibTeX RDF
22	Faisal N. Abu-Khzam, Michael A. Langston	Graph Coloring and the Immersion Order.	COCOON	2003	DBLP DOI BibTeX RDF
19	Davide Bilò, Thomas Erlebach, Matús Mihalák, Peter Widmayer	Discovery of Network Properties with All-Shortest-Paths Queries.	SIROCCO	2008	DBLP DOI BibTeX RDF
19	Dong-Gyu Park, Yang-Soo Kim, Hwan-Gue Cho	Triangle Mesh Compression for Fast Rendering.	IV	1999	DBLP DOI BibTeX RDF	Geometry Modeling, Mesh Compression, Realtime Rendering
18	Brahim Hamid, Bertrand Le Saëc, Mohamed Mosbah 0001	Distributed Local 2-Connectivity Test of Graphs and Applications.	ISPA	2007	DBLP DOI BibTeX RDF
18	Yong Chen, S. H. Son	A fault tolerant topology control in wireless sensor networks.	AICCSA	2005	DBLP DOI BibTeX RDF
18	Monika Rauch Henzinger, Michael L. Fredman	Lower Bounds for Fully Dynamic Connectivity Problems in Graphs.	Algorithmica	1998	DBLP DOI BibTeX RDF	Dynamic planarity testing, Dynamic connectivity testing, Dynamic planarity testing, Dynamic connectivity testing, Lower bounds, Lower bounds, Key words, Cell probe model, Cell probe model
17	Yong Ding 0002, Chen Wang 0010, Li Xiao 0001	An Adaptive Partitioning Scheme for Sleep Scheduling and Topology Control in Wireless Sensor Networks.	IEEE Trans. Parallel Distributed Syst.	2009	DBLP DOI BibTeX RDF
17	Yong Ding 0002, Chen Wang 0010, Li Xiao 0001	A Connectivity Based Partition Approach for Node Scheduling in Sensor Networks.	DCOSS	2007	DBLP DOI BibTeX RDF
17	Frank Kammer, Hanjo Täubig	Connectivity.	Network Analysis	2004	DBLP DOI BibTeX RDF
16	Nicola Galesi, Fariba Ranjbar, Michele Zito 0001	Vertex-connectivity for node failure identification in Boolean Network Tomography.	Inf. Process. Lett.	2024	DBLP DOI BibTeX RDF
16	Chaitanya Nalam, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai	Deterministic k-Vertex Connectivity in k2 Max-flows.	CoRR	2023	DBLP DOI BibTeX RDF
16	Miguel Bosch-Calvo, Fabrizio Grandoni 0001, Afrouz Jabal Ameli	A 4/3 Approximation for 2-Vertex-Connectivity.	CoRR	2023	DBLP DOI BibTeX RDF
16	Wenqian Zhang, Jianfeng Wang	Sharp spectral bounds for the vertex-connectivity of regular graphs.	J. Comb. Optim.	2023	DBLP DOI BibTeX RDF
16	Jørgen Bang-Jensen, Kristine Vitting Klinkby, Pranabendu Misra, Saket Saurabh 0001	A Parameterized Algorithm for Vertex Connectivity Survivable Network Design Problem with Uniform Demands.	ESA	2023	DBLP DOI BibTeX RDF
16	Miguel Bosch-Calvo, Fabrizio Grandoni 0001, Afrouz Jabal Ameli	A 4/3 Approximation for 2-Vertex-Connectivity.	ICALP	2023	DBLP DOI BibTeX RDF
16	Therese Biedl, Karthik Murali	On Computing the Vertex Connectivity of 1-Plane Graphs.	ICALP	2023	DBLP DOI BibTeX RDF
16	Sepehr Assadi, Vihan Shah	Tight Bounds for Vertex Connectivity in Dynamic Streams.	SOSA	2023	DBLP DOI BibTeX RDF
16	Zhiyi Huang, Yaowei Long, Thatchaphol Saranurak, Benyu Wang	Tight Conditional Lower Bounds for Vertex Connectivity Problems.	STOC	2023	DBLP DOI BibTeX RDF
16	Sorrachai Yingchareonthawornchai	Vertex Connectivity via Local Computation: Breaking Quadratic Time, Poly-logarithmic Max-flows, and Derandomization.		2023	RDF
16	Max Franck, Sorrachai Yingchareonthawornchai	Engineering Nearly Linear-time Algorithms for Small Vertex Connectivity.	ACM J. Exp. Algorithmics	2022	DBLP DOI BibTeX RDF
16	Sepehr Assadi, Vihan Shah	Tight Bounds for Vertex Connectivity in Dynamic Streams.	CoRR	2022	DBLP DOI BibTeX RDF
16	Jacob Holm, Ivor van der Hoog, Eva Rotenberg	Worst-case Deterministic Fully-Dynamic Planar 2-vertex Connectivity.	CoRR	2022	DBLP DOI BibTeX RDF
16	Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai	Deterministic Small Vertex Connectivity in Almost Linear Time.	CoRR	2022	DBLP DOI BibTeX RDF
16	Zhiyi Huang, Yaowei Long, Thatchaphol Saranurak, Benyu Wang	Tight Conditional Lower Bounds for Vertex Connectivity Problems.	CoRR	2022	DBLP DOI BibTeX RDF
16	Seth Pettie, Thatchaphol Saranurak, Longhui Yin	Optimal Vertex Connectivity Oracles.	CoRR	2022	DBLP BibTeX RDF
16	Therese Biedl, Karthik Murali	On computing the vertex connectivity of 1-plane graphs.	CoRR	2022	DBLP DOI BibTeX RDF
16	Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai	Deterministic Small Vertex Connectivity in Almost Linear Time.	FOCS	2022	DBLP DOI BibTeX RDF
16	Seth Pettie, Thatchaphol Saranurak, Longhui Yin	Optimal vertex connectivity oracles.	STOC	2022	DBLP DOI BibTeX RDF
16	David L. Rhodes, Breanna N. Johnson	A New Vertex Connectivity Metric.	CoRR	2021	DBLP BibTeX RDF
16	Jason Li 0006, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai	Vertex Connectivity in Poly-logarithmic Max-flows.	CoRR	2021	DBLP BibTeX RDF
16	Therese Biedl, Karthik Murali	Computing the vertex connectivity of a locally maximal 1-plane graph in linear time.	CoRR	2021	DBLP BibTeX RDF
16	Waldo Gálvez, Francisco Sanhueza-Matamala, José A. Soto	Approximation Algorithms for Vertex-Connectivity Augmentation on the Cycle.	CoRR	2021	DBLP BibTeX RDF
16	Max Franck, Sorrachai Yingchareonthawornchai	Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity.	CoRR	2021	DBLP BibTeX RDF
16	Florian Hoersch, Zoltán Szigeti	Eulerian orientations and vertex-connectivity.	Discret. Appl. Math.	2021	DBLP DOI BibTeX RDF
16	Jun Liang 0002, Dingjun Lou, Zan-Bo Zhang	The cubic graphs with finite cyclic vertex connectivity larger than girth.	Discret. Math.	2021	DBLP DOI BibTeX RDF
16	Max Franck, Sorrachai Yingchareonthawornchai	Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity.	SEA	2021	DBLP DOI BibTeX RDF
16	Waldo Gálvez, Francisco Sanhueza-Matamala, José A. Soto	Approximation Algorithms for Vertex-Connectivity Augmentation on the Cycle.	WAOA	2021	DBLP DOI BibTeX RDF
16	Jason Li 0006, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai	Vertex connectivity in poly-logarithmic max-flows.	STOC	2021	DBLP DOI BibTeX RDF
16	Hao Li 0061, Xin Gao	On the Vertex-Connectivity of an Uncertain Random Graph.	IEEE Access	2020	DBLP DOI BibTeX RDF
16	Mehdi Djellabi, Bertrand Jouve, Frédéric Amblard	Dense and sparse vertex connectivity in networks.	J. Complex Networks	2020	DBLP DOI BibTeX RDF
16	Dejin Qin, Yingzhi Tian, Laihuan Chen, Jixiang Meng	Cyclic vertex-connectivity of Cartesian product graphs.	Int. J. Parallel Emergent Distributed Syst.	2020	DBLP DOI BibTeX RDF
16	Lukas Gianinazzi, Torsten Hoefler	Parallel Planar Subgraph Isomorphism and Vertex Connectivity.	CoRR	2020	DBLP BibTeX RDF
16	Mehdi Djellabi, Bertrand Jouve, Frédéric Amblard	Dense and sparse vertex connectivity in networks.	CoRR	2020	DBLP BibTeX RDF
16	Suil O	The second largest eigenvalue and vertex-connectivity of regular multigraphs.	Discret. Appl. Math.	2020	DBLP DOI BibTeX RDF
16	Zuwen Luo, Liqiong Xu	A Kind Of Conditional Vertex Connectivity Of Cayley Graphs Generated By Wheel Graphs.	Comput. J.	2020	DBLP DOI BibTeX RDF
16	Hiroaki Kata, Seiya Ueno	Decentralized Robust k-connected Network with Unmanned Vehicles Using Vertex Connectivity.	SICE	2020	DBLP BibTeX RDF
16	Lukas Gianinazzi, Torsten Hoefler	Parallel Planar Subgraph Isomorphism and Vertex Connectivity.	SPAA	2020	DBLP DOI BibTeX RDF
16	Ruifang Liu, Hong-Jian Lai, Yingzhi Tian, Yang Wu 0007	Vertex-connectivity and eigenvalues of graphs with fixed girth.	Appl. Math. Comput.	2019	DBLP DOI BibTeX RDF
16	Sergey Goryainov, Dmitry Panasenko	On vertex connectivity of Deza graphs with parameters of the complements to Seidel graphs.	Eur. J. Comb.	2019	DBLP DOI BibTeX RDF
16	Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai	Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme.	CoRR	2019	DBLP BibTeX RDF