Network Dynamics and Simulation Science Laboratory

URL: http://ndssl.vbi.vt.edu/index.php

Contact: Christopher Barrett

The NDSSL is pursuing an advanced research and development program for interaction-based modeling, simulation, and associated analysis, experimental design, and decision support tools for understanding large biological, information, social, and technological systems. Extremely detailed, multi-scale computer simulations allow formal and experimental investigation of these systems. The need for such simulations is derived from questions posed by scientists, policy makers, and planners involved with very large complex systems. The simulation applications are underwritten by a theoretical program in discrete mathematics and theoretical computer science that is sustained by more than a decade of experience with the interplay of research and application. Laboratory members are currently pursuing active projects in Wireless Networks, Computational Epidemiology and Algorithms, Complex Networks and High Performance Computing.

2012
Zhao, Z., G. Wang, A. R. Butt, and M. M. V. and Maleq Khan, V. S. Anil Kumar, "SAHAD: Subgraph Analysis in Massive Networks Using Hadoop.", Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 05/2012.
2008
Choi, Y., M. Khan, A. V. S. Kumar, and G. Pandurangan, "Work-Efficient Distributed Euclidean Minimum Spanning Tree,", 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Munich, Germany, June , 2008.
Barrett, C., K. Bisset, G. Konjevod, M. Holzer, M. Marathe, and D. Wagner, "Engineering Label-Constrained Shortest-Path Algorithms,", Proc. 4th International Conference on Algorithmic Aspects in Information and Management (AAIM 2008 ), June, 2008.
Barrett, C., S. Eubank, and M. Marathe, "An Interaction-Based Approach to Computational Epidemiology", Proc. Computability in Europe 2008, Logic and Theory of Algorithms , 2008.
Chafekar, D., D. Levin, A. V. S. Kumar, M. Marathe, S. Parthasarathy, and A. Srinivasan, "Capacity of Asynchronous Random-Access Scheduling in Wireless Networks", Proc. 27th IEEE International Conference on Computer Communications (INFOCOM) , 2008 , 2008.
Kumar, V. S. A., M. Marathe, S. Parthasarathy, and A. Srinivasan, "Minimum Weighted Completion Time", Encyclopedia of Algorithms , M. Kao, Ed: Springer Verlag, 2008.
Barrett, C., S. Eubank, B. Lewis, and M. Marathe, "Information Systems for Detection and Management of Pandemics", Encyclopedia of Geographic Information Systems, S. Shekhar, X. Xiong, Eds. : Springer-Verlag, 2008.
2007
Atkins, K., J. Chen, A. V. S. Kumar, and A. Marathe, "Structural Properties of Electrical Networks.", International Journal of Critical Infrastructure, 2007.
Eubank, S., A. V. S. Kumar, and M. Marathe, Epidemiology and wireless communication tight analogy or loose metaphor, : Bio-Inspired Computing and Communication, Springer Verlag. In press, 2007.
Barrett, C., B. Lewis, J. Chen, A. V. S. Kumar, S. Eubank, M. Marathe, and H. Mortveit, "Interactions among human behavior, social networks, and societal infrastructures: A case study in computational epidemiology.", Ravi S, Shukla S (eds.), Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz. Springer Verlag, Vol. In press December, 2007.
Barrett, C., K. Bisset, S. Eubank, A. V. S. Kumar, M. Marathe, and H. Mortveit, "Modeling and Simulation of Large Biological, Information and Socio-Technical Systems: An Interaction-Based Approach", Proceedings of the Short Course on Modeling and Simulation of Biological Networks, AMS Lecture Notes, Series: PSAPM, revised and accepted, January 2007. In Press., 2007.
Chafekar, D., A. V. S. Kumar, M. Marathe, S. Parthasarathy, and A. Srinivasan, "Cross-Layer Latency Minimization in Wireless Networks with SINR constraints", Proc. 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), September, 2007.
Kumar, A. V. S., M. Marathe, S. Parthasarathy, and A. Srinivasan, "Provable algorithms for joint optimization of transport, routing and MAC layers in wireless ad hoc networks", Proc. Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM)-Principles of Mobile Computing (POMC) , 2007.
Thomas, R. W., L. A. DaSilva, M. Marathe, and K. N. Wood, "Critical Design Decisions for Cognitive Networks", Proc. ICC Wireless Adhoc and Sensor Networks Symposium, 2007.
Barrett, C., H. H. B. III, M. Marathe, S. S. Ravi, D. J. Rosenkrantz, R. E. Stearns, and M. Thakur, "Computational Aspects of Analyzing Social Network Dynamics", Proc. International Joint Conference on Artificial Intelligence, (IJCAI 07), Hyderabad, India, pp. 2268-2273, January, 2007.
Barrett, C., K. Bisset, S. Eubank, V. S. A. Kumar, M. Marathe, and H. S. Mortveit, "Modeling and Simulation of Large Biological, Information and Socio-Technical Systems: An Interaction-Based Approach ", Proceedings of the Symposia in Applied Mathematics, Short Course on Modeling and Simulation of Biological Networks, AMS Lecture Notes, Series, (PSAPM) 64, pp. 101-147, 2007.
2006
Kumar, A. V. S., M. Marathe, S. Parthasarathy, and A. Srinivasan, "Provable Algorithms for Parallel Generalized Sweep Scheduling.", Journal of Parallel and Distributed Computing, vol. 66, no. 6, pp. 807-821, 2006.
Duncan, C., S. Kobourov, and A. V. S. Kumar, "Optimal Constrained Graph Exploration", Transactions of Algorithms, vol. 2, no. 3, pp. 380-402, 2006.
Eidenbenz, S., A. V. S. Kumar, and S. Zust, "Equilibria in Topology control games for ad hoc networks", Mobile Networks and Applications, vol. 11, pp. 143-159, 2006.
Chen, J., A. V. S. Kumar, A. Marathe, and K. Atkins, "Model Based Spatial Data Mining for Power Markets.", SIAM-DM 2006 Workshop on Spatial Data Mining, April, 2006.
Atkins, K., J. Chen, A. V. S. Kumar, and A. Marathe, "Structural Properties of Electrical Networks", 3rd International Conference on Critical Infrastructures, Septermber, 2006.
Barrett, C., G. Istrate, A. V. S. Kumar, M. Marathe, S. Thite, and S. Thulasidasan, "Strong Edge Coloring for Channel Assignment in Wireless Radio Networks.", IEEE International Workshop on ”Foundation and Algorithms for Wireless Networking (FAWN’2006), 2006.
Kumar, A. V. S., M. Marathe, M. T. R. Sundaram, and S. Thulasidasan, "Scaling Laws for the Internet over Urban Regions, ", CAIDA (Cooperative Association for Internet Data Analysis), ISMA 2006 WIT: Workshop on the Internet Topology , 2006.
Chen, J., M. Marathe, R. Rajaraman, and R. Sundaram, "The Confluent Capacity of the Internet: Congestion vs. Dilation", Proceedings of IEEE International Conference on Distributed Computing Systems (ICDCS ), 2006.
Istrate, G., A. Hansson, M. Marathe, S. Thulasidasan, and C. Barrett, "Semantic compression of TCP traces, ", Proceedings of the IFIP NETWORKING Conference, F. Boavida et al. (editors), pp. 123-135, 2006.
Barrett, C., G. Istrate, A. V. S. Kumar, M. Marathe, S. Thite, and S. Thulasidasan, "Strong Edge Coloring for Channel Assignment in Wireless Radio Networks", Proceedings of the First IEEE International Workshop on Foundations and Algorithms for Wireless Networking (FAWN'06) , pp. 106-110, 2006.
Barrett, C., S. Eubank, and M. Marathe, "Modeling and Simulation of Large Biological, information and Socio-Technical Systems: An Interaction Based Approach ", Interactive Computing: A new Paradigm, Ed. D. Goldin, S. Smolka and P. Wegner: Springer Verlag, pp. 353-394, 2006.
2005
Kumar, A. V. S., M. Marathe, S. Parthasarathy, and A. Srinivasan, "Approximation Algorithms for Scheduling on Multiple Machines.", Proc. of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2005.
Barrett, C., M. Drozda, D. Engelhart, A. V. S. Kumar, M. Marathe, M. Morin, S. S. Ravi, and J. P. Smith, "Understanding Protocol Performance and Robustness of Ad hoc Networks Through Structural Analysis", Proc. International Conference onWireless and Mobile Computing, Networking and Communications (WiMob 2005), 2005.
Liu, R., E. Lloyd, M. Marathe, R. Ramanathan, and S. Ravi, "Algorithmic Aspects of Topology Control Problems For Ad-hoc Networks", ACM/Baltzer J. Mobile Networks and Applications (MONET), vol. 10, pp. 19-34, 2005.
Barrett, C., S. Eidenbenz, L. Kroc, M. Marathe, and J. Smith, "Parametric Probabilistic Routing in Sensor Networks", ACM/Baltzer J. Mobile Networks and Applications (MONET), vol. 10, no. 4, pp. 529-544, 2005.
Kumar, A. V. S., M. Marathe, S. Parthasarathy, and A. Srinivasan, "Approximation Algorithms for Scheduling on Multiple Machines ", Proc. 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pp. 254-263 , 2005.
Barrett, C., M. Morin, C. Engelhart, M. Marathe, J. Smith, M. Drozda, and A. V. Kumar, "Understanding Protocol Performance and Robustness of Ad-Hoc Networks Through Structural Analysis ", Proc. IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob) , 2005.
Eubank, S., A. V. Kumar, M. Marathe, A. Srinivasan, and N. Wang, "Structural and Algorithmic Aspects of Massive Social Networks", Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 718-727, 2005.
III, H. H. B., M. Marathe, R. E. Stearns, and D. J. Rosenkrantz, "A Survey of Periodically Specified Problems", Computational Complexity and Statistical Physics , Oxford University Press, Santa Fe Institute Lectures in the Sciences of Complexity , G. Istrate, C. Moore, A. Percus Eds, pp. 285-318, 2005.
2004
Konjevod, G., S. Krumke, and M. Marathe, "Budget Constrained Minimum Cost Connected Medians", Journal of Discrete Algorithms, vol. 2, no. 4, pp. 453-469, 2004.
2003
Kumar, A. V. S., and R. Hariharan, "Covering Rectilinear Polygons with Axis-Parallel Rectangles", SIAM Journal of Computing, vol. 32, no. 6, pp. 1509-1541, 2003.
Chandru, V., A. DuttaSharma, and A. V. S. Kumar, "The Algorithmics of Folding Proteins on Lattices", Discrete Applied Mathematics, vol. 127, no. 1, pp. 145-161, 2003.
Eidenbenz, S., A. V. S. Kumar, and S. Zust, "Equilibria in Topology control games for ad hoc networks", proceedings of the Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications and Principles of Mobile Computing (DIALPOMC), Septermber, 2003.
Krumke, S., R. Liu, E. Lloyd, M. Marathe, R. Ramanathan, and S. Ravi, "Topology Control Problems Under Symmetric and Asymmetric Thresholds", Proc. International Conference on Ad hoc and Wireless Networks (ADHOC-NOW'03) , Montreal, Canada, pp. 187--198, October , 2003.
Barrett, C., S. Eidenbenz, L. Kroc, M. Marathe, and J. Smith, "Parametric Probabilistic Sensor Network Routing", Proc. 2nd ACM International Workshop on Wireless Sensor Networks (WSNA'03) , San Deigo, pp. 122-131, 2003.
Burch, C., R. Carr, S. Krumke, M. Marathe, C. Phillips, and E. Sundberg, "A decomposition-based pseudoapproximation algorithm for network flow inhibition ", Network Interdiction and Stochastic Integer Programming , D.L. Woodruff (ed): Kluwer Academic Press, pp. 51-68, 2003.
2002
Kumar, A. V. S., and M. Marathe, "Improved Results for Stackelberg Scheduling Strategies.", The 29th International Colloquium on Automata, Languages and Programming, 2002 (ICALP), Lecture Notes in Computer Science, 2380, Springer, 2002.
Doddi, S., M. Marathe, and B. Moret, "Point Set Labeling with Specified Positions", International Journal of Computational Geometry, vol. 12, no. 1-2, pp. 29-66, 2002.
Barrett, C., M. Marathe, S. S. Ravi, and J. Smith, "A Mobility and Traffic Generation Framework for Modeling and Simulating Ad~hoc Communication Networks ", Proc. 6th ACM Symposium on Applied Computing (SAC), Madrid, Spain, pp. 122-126, March, 2002.
Barrett, C., C. Engelhart, M. Marathe, and A. Sivasubramanium, "Analyzing the Short-Term Fairness of IEEE 802.11 in Wireless Multi-hop Radio Networks ", Proc. 10th IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, (MASCOTS'02) , October , 2002.
Marathe, M., "Towards a Predictive Complexity Theory", Proc. 29th International Colloquium on Automata Languages and Programming , , Malaga, Spain, pp. 22-31, 2002.
Marathe, M., "Routing in Very large Multi-Modal Time Dependent Networks: Theory and Practice", Proc. Algorithmic MeThods and Models for Optimization of RailwayS (ATMOS 2002) , Malaga, Spain, 2002.
Anil, V. S., and M. Marathe, "Improved Results for Stackelberg Scheduling Strategies", 29th International Colloquium on Automata Languages and Programming, Malaga, Spain, pp. 776-787, 2002.
Krumke, S., M. Marathe, D. Poensgen, S. Ravi, and H. Wirth, "Budgeted Maximum Graph Coverage, ", Proc. 28th International Workshop on Graph Theoretic Concepts in Computer Science, (WG), Cesky, Czech Republic, August , 2002.
Barrett, C., M. Drozda, A. Marathe, and M. Marathe, "Characterizing the Interaction Between Routing and MAC Protocols in Ad-hoc Networks, ", 3rd ACM international Symposium on Mobile Ad Hoc Networking and Computing, Lausanne, Switzerland, pp. 92-103, June , 2002.
Liu, R., E. Lloyd, M. Marathe, R. Ramanathan, and S. Ravi, "Algorithmic Aspects of Topology Control Problems For Ad-hoc Networks", 3rd ACM international Symposium on Mobile Ad Hoc Networking and Computing, Lausanne, Switzerland, June , 2002.
Barrett, C., M. Drozda, and M. Marathe, "A Comparative Experimental Study of Media Access Protocols for Wireless Radio Networks ", Proc. IEEE Wireless Communications and Networking Conference (WCNC): Florida , pp. 405-411, 2002.
Barrett, C., S. Eubank, M. Marathe, H. Mortveit, and C. Reidys, "Science and Engineering of Large Scale Socio-Technical Simulations", Proc. 1st International Conference on Grand Challenges in Simulations, San Antonio Texas, 2002.
2001
Kumar, A. V. S., and R. Hariharan, "Markovian Coupling v/s Conductance for the Jerrum-Sinclair Chain.", Random Structures and Algorithms, vol. 18, no. 1, pp. 1-17, 2001.
Duncan, C., S. Kobourov, and A. V. S. Kumar, "Optimal Constrained Graph Exploration", Proceedings of the 12th ACM Symposium on Discrete Algorithms (SODA), pp. 807-814, 2001.
Krysta, P., and A. V. S. Kumar, "Approximation algorithms for minimum size 2-connectivity problems.", Proceedings of the 18th International Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, n. 2010, Springer, pp. 431- 442, 2001.
Barrett, C., R. Jacob, and M. Marathe, "Formal Language Constrained Path Problems", SIAM J. Computing, vol. 30, no. 3, pp. 809-837, June, 2001.
Krumke, S. O., M. Marathe, H. Noltemeier, S. S. Ravi, and H. C. Wirth, "Upgrading Bottleneck Constrained Forests", Discrete Applied Mathematics, vol. 108, no. 1-2, pp. 129-142, 2001.
Barrett, C., H. H. B. III, M. Marathe, S. S. Ravi, D. J. Rosenkrantz, R. E. Stearns, and P. Tosic, "Garden of Eden and Fixed Point Configurations in Sequential Dynamical Systems ", Proc. International Conference on Discrete Models in Combinatorics, Computation and Geometry (DM-CCG) , pp. 95-110, June, 2001.
Istrate, G., M. Marathe, and S. S. Ravi, "Adversarial Models in Evolutionary Game Dynamics, 2001", Proc. 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 719-720, January , 2001.
2000
Kumar, A. V. S., S. Arya, and R. Hariharan, "Hardness of Set Covering with Intersection 1", Proceedings of the 27th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol 1853, pp 624-635, 2000, 2000.
Doddi, S., M. Marathe, and B. Moret, "Point Set Labeling with Specified Positions", Proc. ACM Symposium on Computational Geometry (SoCG) , Hong Kong, pp. 182-190, June, 2000.
Dowell, L. J., M. Drozda, B. Henderson, V. Loose, M. Marathe, and D. Roberts, "Scalability of ELISIMS: Comprehensive Detailed Simulation of Electric Power Industry ", Proc. IEEE International Conference on Systems, Man and Cybernetics, (SMC) , Nashville, October , 2000.
Doddi, S., M. Marathe, R. S. S. D. Taylor, and P. Widmayer, "Approximation algorithms for clustering to minimize the sum of diameters ", Proc. 7th Scandinavian Workshop on Algorithm Theory, (SWAT) July, Bergen, Norway, July, 2000.
Marathe, M., S. Krumke, and M. Marathe, "Budget Constrained Minimum Cost Connected Medians", Proc. 26th International Workshop on Graph Theoretic Concepts in Computer Science, (WG) Proc. 26th International Workshop on Graph Theoretic Concepts in Computer Science, (WG) , Konsantz, Germany, June, 2000.
Marathe, M., L. D. Risenger, and A. Panconesi, "Experimental Analysis of a Simple Distributed Edge Coloring Algorithm ", Proc. 12th ACM Symposium on Parallel Algorithms and Architectures, (SPAA), Maine, pp. 166-175, July , 2000.
Carr, R., S. Doddi, G. Konjevod, and M. Marathe, "On the Red-Blue Set Cover Problem", Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 345-353, January , 2000.
Czabarka, E., G. Konjevod, M. Marathe, A. G. Percus, and D. C. Torney, "Algorithms for Optimizing Production DNA Sequencing", Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 399-408, January , 2000.
Cook, D., V. Faber, G. Hicks, M. Marathe, A. Srinivasan, and Y. Sussmann, "Combinatorial Problems Arising in Deregulated Electrical Power Industry: Survey and Future Directions ", Proc. Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems , P. M. Pardalos, Editor: Kluwer Academic Publishers, pp. 138-162, 2000.
III, H. H. B., R. E. Stearns, and M. Marathe, "On the Efficient Approximability of "HARD" Problems: A Survey", Proc. Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems , P. M. Pardalos, Editor: Kluwer Academic Publishers, pp. 308-322, 2000.
1999
Kumar, A. V. S., and R. Hariharan, "Markovian Coupling v/s Conductance for the Jerrum-Sinclair Chain", Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 241-252, 1999.
Kumar, A. V. S., and R. Hariharan, "Covering Rectilinear Polygons with Axis-Parallel Rectangles", Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 445-454, 1999.
1996
Kumar, A. V. S., "Recognition of Counting and Balancing Networks is Hard", National Seminar on Theoretical Computer Science, India, July, 1996.